括号问题中的堆栈实现错误

Question

我正在解决leet代码上的堆栈问题。许多测试用例已经通过。它只是失败了“{[]}”

que- https://leetcode.com/problems/valid-parentheses/description/ 我的提交-https://leetcode.com/problems/valid-parentheses/submissions/1202908225/

我不明白为什么代码不适用于这个特定的测试用例。 我无法发现错误

代码-

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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)
{
    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
}

Answer 1

问题在于，您在函数返回之前没有清理链表，并且下次调用

isValid

函数时，之前的列表仍然存在 - 并且可能不为空，从而影响了结果下次通话。

为了解决这个问题，您不应该将

head

定义为全局变量，而应定义为

isValid

的局部变量，并且还可以通过释放仍为列表中的节点分配的内存来避免内存泄漏。

// 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; 
}