使用栈实现Valid Parentheses的C代码本地正常但LeetCode提交失败

问题根源 #

你的代码核心问题是使用了全局栈变量，LeetCode判题系统会多次调用isValid函数测试不同用例，全局栈的状态会保留上一次调用的结果，导致后续测试用例的栈初始状态错误。比如第一次测试{[]}后栈被清空，但下一次测试前栈未重置，就会出现逻辑错误。

另外，栈的pull和top函数存在逻辑漏洞：

• 栈为空（stack.free == stack.size）时，pull返回*(stack.top)会访问无效内存
• push函数中stack.top的移动逻辑不严谨，可能导致指针越界

修复后的代码 #

方案1：每次调用前重置全局栈 #

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

typedef struct Stack{
    int size;
    int free;
    char *buff;
    char *top;
}Stack; 

Stack stack = {
    .size = 0,
    .free = 0,
    .buff = NULL,
    .top = NULL
}; 

void resetStack() {
    free(stack.buff);
    stack.size = 0;
    stack.free = 0;
    stack.buff = NULL;
    stack.top = NULL;
}

void push(char c){
    if (stack.free == 0){
        stack.buff = realloc(stack.buff, stack.size + 10);
        if (stack.size == 0) stack.top = stack.buff;
        stack.size += 10;
        stack.free += 10;
    }
    *(stack.top) = c; 
    --stack.free;
    stack.top++; // 存入数据后直接移动top指针，逻辑更清晰
}

char pull(){
    if (stack.free == stack.size) { // 栈为空时直接返回-1
        return -1;
    }
    stack.top--;
    char tmp = *(stack.top);
    stack.free++;
    return tmp;
}

char top(){
    if (stack.free == stack.size) { // 栈为空时直接返回-1
        return -1;
    }
    return *(stack.top - 1);
}

#define OP '(' 
#define CP ')' 
#define OB '['
#define CB ']'
#define OC '{'
#define CC '}'

bool isCorrectChar(char expected_ch){
    if (top() == expected_ch){
        pull();
        return true;
    }else{
        return false; 
    } 
}

bool isValid(char* s) {
    resetStack(); // 每次调用前强制重置栈状态
    int len = strlen(s);
    if (len % 2 != 0) return false;
    char c;
    while ((c = *s++) != '\0'){
        switch (c){
            case OP:
            case OB:
            case OC:
                push(c);
                break;
            case CP:
                if (!isCorrectChar(OP)) return false;
                break;
            case CB:
                if (!isCorrectChar(OB)) return false;
                break;
            case CC:
                if (!isCorrectChar(OC)) return false;
                break;
            default:
                return false;
        }
    }
    return stack.free == stack.size;
}

方案2：使用局部栈（更推荐，无全局变量副作用） #

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

typedef struct Stack{
    int size;
    int count; // 用count记录栈中元素数量，逻辑更直观
    char *buff;
}Stack; 

Stack* createStack(int initSize) {
    Stack *s = malloc(sizeof(Stack));
    s->buff = malloc(initSize * sizeof(char));
    s->size = initSize;
    s->count = 0;
    return s;
}

void push(Stack *s, char c) {
    if (s->count == s->size) {
        s->size *= 2;
        s->buff = realloc(s->buff, s->size * sizeof(char));
    }
    s->buff[s->count++] = c;
}

char pop(Stack *s) {
    if (s->count == 0) return -1;
    return s->buff[--s->count];
}

char peek(Stack *s) {
    if (s->count == 0) return -1;
    return s->buff[s->count - 1];
}

void destroyStack(Stack *s) {
    free(s->buff);
    free(s);
}

#define OP '(' 
#define CP ')' 
#define OB '['
#define CB ']'
#define OC '{'
#define CC '}'

bool isValid(char* s) {
    int len = strlen(s);
    if (len % 2 != 0) return false;
    
    Stack *stack = createStack(10);
    char c;
    while ((c = *s++) != '\0'){
        switch (c){
            case OP:
            case OB:
            case OC:
                push(stack, c);
                break;
            case CP:
                if (peek(stack) != OP) {
                    destroyStack(stack);
                    return false;
                }
                pop(stack);
                break;
            case CB:
                if (peek(stack) != OB) {
                    destroyStack(stack);
                    return false;
                }
                pop(stack);
                break;
            case CC:
                if (peek(stack) != OC) {
                    destroyStack(stack);
                    return false;
                }
                pop(stack);
                break;
            default:
                destroyStack(stack);
                return false;
        }
    }
    bool result = (stack->count == 0);
    destroyStack(stack);
    return result;
}

关键修复说明 #

1. 全局栈重置：方案1新增resetStack函数，每次调用isValid前清空栈内存、重置所有状态，彻底避免多测试用例的状态残留。
2. 栈操作逻辑修正：优化push、pull、top函数的边界判断，避免访问无效内存，简化指针移动逻辑。
3. 局部栈方案：完全抛弃全局变量，每次调用isValid创建独立栈，使用count替代复杂的free/size计数，逻辑更简洁，从根源上解决多调用干扰问题。

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