在 c 中使用堆栈的有效括号

Question

我正在解决问题20。 Leetcode 中使用 c 的有效括号，当他们检查此输入 s ="{[]}" 时，代码返回 false 而不是 true，但我没有看到代码有任何问题：

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

int isEmpty(stack p){
    return p ==NULL;
}

void push(stack *p,char x){
    node *new = (node*)malloc(sizeof(node));
    new->data = x;
    new->next = *p;
    *p = new;
}

void pop(stack *p){
    node *t=*p;
    *p=(*p)->next;
    free(t);
}
bool isValid(char* s) {
    stack p;
    if(s[1] == '\0') return false;

    for(int i=0;s[i]!= '\0';++i){
        if(s[i]=='(' || s[i]=='[' || s[i]=='{'){
            push(&p,s[i]);
        }
        else{
            if((s[i]==')' && p->data == '(')||(s[i]==']' && p->data == '[') || (s[i]=='}' && p->data == '{'))
                pop(&p);
            else return false;
        }
    }
    return isEmpty(p);
}

我真的没有看到代码有任何问题，如果您有任何建议，请帮忙！

Answer 1

函数

isValid

具有未定义的行为（它是

isInValid

:)）。

对于初学者来说，指针

p

未初始化并且具有不确定的值

stack p;

其次，考虑字符串“]”。对于这样的字符串，控制将传递给 if 语句

 if((s[i]==')' && p->data == '(')||(s[i]==']' && p->data == '[') || (s[i]=='}' && p->data == '{'))

因此，即使指针

p

将被初始化为空指针，像

p->data

这样的表达式也会尝试使用空指针访问内存。

我认为如果是空字符串，函数应该返回逻辑 true。