stack implementation error in brackets problem

Question

I am solving a LeetCode problem 20. Valid Parentheses:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.
• Every close bracket has a corresponding open bracket of the same type.

Many testcases have been passed. It just fails for "{[]}"

My submission: https://leetcode.com/problems/valid-parentheses/submissions/1202908225/

My code

typedef struct node
{
    char data;
    struct node *next;
} node;

node *head = NULL;

int isEmpty(node *head)
{
    return head == NULL;
}

node *pop(node *head)
{
    node *temp = head;
    head = head->next;
    free(temp);
    return head;
}

node *push(node *head, char a)
{
    if (head == NULL)
    {
        head = (node *)malloc(sizeof(node));
        head->data = a;
        head->next = NULL;
        return head;
    }
    else
    {
        node *temp = (node *)malloc(sizeof(node));
        temp->data = a;
        temp->next = head;
        return temp;
    }
}

char peek(node *head)
{
    return head->data;
}

bool isValid(char *s)
{
    int len = strlen(s);

    for (int i = 0; i < len; i++)
    {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[')
        {
            head = push(head, s[i]);
        }
        else
        {
            if (isEmpty(head)) // Check if stack is empty
            {
                return false;
            }
            else if ((s[i] == ')' && peek(head) == '(') ||
                     (s[i] == '}' && peek(head) == '{') ||
                     (s[i] == ']' && peek(head) == '['))
            {
                head = pop(head);
            }
            else
            {
                return false;
            }
        }
    }

    return isEmpty(head); // Check if stack is empty after processing all characters
}

I can't figure out why the code isn't working for this specific test case.

Where is my mistake?

Answer 1

The problem is that you don't clean up your linked list before the function returns, and that the next time the isValid function is called, the previous list is still there -- and possibly not empty, influencing the result of that next call.

To solve this, you should not define head as a global variable, but as a variable local to isValid, and also avoid leaking memory, by freeing the memory you still have allocated for nodes in the list.

So, to keep the changes to your code at a minimum, we can make it work like this:

// Add this function for removing all nodes from a list
node* clear(node *head) {
    while (head) {
        head = pop(head);
    }
    return NULL;
}

bool isValid(char *s)
{
    node *head = NULL; // Local variable!
    int len = strlen(s);

    for (int i = 0; i < len; i++)
    {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[')
        {
            head = push(head, s[i]);
        }
        else
        {
            if (isEmpty(head)) 
            {
                return false;
            }
            else if ((s[i] == ')' && peek(head) == '(') ||
                     (s[i] == '}' && peek(head) == '{') ||
                     (s[i] == ']' && peek(head) == '['))
            {
                head = pop(head);
            }
            else
            {
                head = clear(head); // Avoid leaking memory
                return false;
            }
        }
    }
    bool result = isEmpty(head);
    head = clear(head); // Avoid leaking memory
    return result; 
}