C语言栈实现LeetCode有效括号问题：输入"{[]}"返回false求排查

核心问题点 #

• 栈指针未初始化：isValid函数里的stack p;没有初始化为NULL，属于野指针。后续push操作和访问p->data都会触发未定义行为，这是"{[]}"返回false的核心原因。
• 错误的前置判断：开头的if(s[1] == '\0') return false;完全错误——比如合法输入"()"会被直接判定为无效，且空字符串访问s[1]会触发越界。
• 右括号处理未检查栈空：遇到右括号时没有先判断栈是否为空，若输入以右括号开头（如"]"），直接访问p->data会导致程序崩溃。

修正后的代码 #

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

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 = (node*)malloc(sizeof(node));
    new_node->data = x;
    new_node->next = *p;
    *p = new_node;
}

void pop(stack *p){
    if(isEmpty(*p)) return; // 增加空栈判断，避免崩溃
    node *t = *p;
    *p = (*p)->next;
    free(t);
}

bool isValid(char* s) {
    stack p = NULL; // 初始化栈为NULL，避免野指针
    
    for(int i = 0; s[i] != '\0'; ++i){
        if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
            push(&p, s[i]);
        }
        else{
            // 先判断栈是否为空，无匹配左括号直接返回false
            if(isEmpty(p)) return false;
            // 匹配则弹出，否则返回false
            if((s[i] == ')' && p->data == '(') || 
               (s[i] == ']' && p->data == '[') || 
               (s[i] == '}' && p->data == '{')){
                pop(&p);
            } else {
                return false;
            }
        }
    }
    // 最终检查栈是否为空，确保所有左括号都完成匹配
    return isEmpty(p);
}

关键修改说明 #

1. 初始化栈指针：stack p = NULL;彻底解决野指针问题。
2. 移除错误前置判断：遵循LeetCode题目要求，空字符串为有效输入，同时避免越界访问。
3. 右括号前置空栈检查：遇到右括号时先确认栈内有可匹配的左括号，避免空指针访问。
4. 增强pop函数鲁棒性：增加空栈判断，防止非法调用导致崩溃。
5. 变量名优化：将new改为new_node，避免与C++关键字混淆（C中虽允许，但更规范）。

内容的提问来源于stack exchange，提问作者roger_hai