使用动态内存构建C语言栈遇问题：free()无效指针及结果错误

核心问题拆解 #

你的代码存在两个致命问题：内存操作错误导致free(): invalid pointer，以及栈的逻辑实现错误导致匹配结果不正确。

1. 内存错误原因 #

你错误地通过移动栈的底层数组指针s->v来实现pop和destroy，违反了内存管理的基本规则：

• malloc/realloc返回的指针是内存块的起始地址，绝对不能随意修改这个指针，否则free时会指向非法地址，触发valgrind检测到的Invalid free()错误。
• pop函数里的s->v--和destroy里的s->v -= s->sz +1完全是多余且错误的操作，栈的元素管理应该通过sz（当前元素个数）标记，而非移动数组指针。

2. 栈逻辑错误原因 #

栈是**后进先出（LIFO）**的数据结构，但你的实现完全不符合这个规则：

• top函数返回数组第一个元素（*(s->v)），而非栈顶元素（最后入栈的元素）。
• pop函数同样取数组第一个元素再移动指针，颠倒了栈的操作逻辑，导致括号匹配判断完全错误。

3. 额外边界问题 #

当遇到右括号但栈为空时，pop返回-1，此时match函数会用-1和右括号比较，逻辑上应直接判定为不合法，而非进入匹配判断。

修正后的完整代码 #

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

typedef struct {
    int *v;    
    int cap;    
    int sz;
} stack;

stack *build() {
    stack *new_stack = (stack *)malloc(sizeof(stack));
    new_stack->v = (int *)malloc(sizeof(int) * 4);
    new_stack->cap = 4;
    new_stack->sz = 0;
    return new_stack;
}

int is_empty(stack *s) {
    return s->sz == 0;
}

int push(stack *s, int e) {
    int success = 1;

    if (s->sz == s->cap) {
        // 扩容改为每次翻倍，比逐次+1效率更高
        int *tmp = (int *)realloc(s->v, s->cap * 2 * sizeof(int));
        if ((success = tmp != NULL)) {
            s->v = tmp;
            s->cap *= 2;
        }
    }

    if (success) {
        s->v[s->sz++] = e;
    }

    return success;
}

// 获取栈顶元素，栈空时返回-1
int top(stack *s) {
    if (is_empty(s))
        return -1;
    return s->v[s->sz - 1];
}

// 弹出栈顶元素，栈空时返回-1
int pop(stack *s) {
    if (is_empty(s))
        return -1;
    return s->v[--s->sz];   
}

void destroy(stack *s) {
    // 直接释放malloc返回的原始指针即可
    free(s->v);
    free(s);
}

// 判断左右括号是否匹配
int match(char p1, char p2) {
    return (p1 == '(' && p2 == ')') ||
           (p1 == '[' && p2 == ']') ||
           (p1 == '{' && p2 == '}');
}

int main() {
    int c;
    stack *s = build();
    while ((c = getchar()) != EOF && c != '\n') {
        if (c == '(' || c == '[' || c == '{') {
             push(s, c);
        } else if (c == ')' || c == ']' || c == '}') {
            int top_char = pop(s);
            // 栈空或者括号不匹配，直接判定非法
            if (top_char == -1 || !match(top_char, c)) {
                printf("no\n");
                destroy(s);
                return 0;
            }
        }
    }
    puts(is_empty(s) ? "yes" : "no");
    destroy(s);
    return 0;
}

关键修正点说明 #

• 栈操作完全基于sz变量：push时将元素放在v[sz]后sz++，pop时先sz--再返回v[sz]，严格遵循后进先出逻辑。
• 内存释放直接使用malloc/realloc返回的原始指针s->v，避免任何指针偏移操作。
• 扩容策略改为每次翻倍，减少realloc调用次数，提升效率。
• 增加栈空时弹出的判断，提前终止非法情况的处理流程。

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