使用Stack实现C语言括号匹配程序无输出问题求助

核心问题原因 #

• 野指针访问错误：在parenthesisMatch函数中，你仅定义了栈结构体指针struct stack* sp，但没有为该指针分配对应的结构体内存空间，就直接对sp->size、sp->top等成员赋值，属于非法内存访问，会触发未定义行为，导致程序运行崩溃，无法得到预期输出。
• 额外优化点：原代码存在内存泄漏问题，函数结束前需要手动释放sp->arr和sp本身占用的堆内存。

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
//栈结构定义
struct stack
{
    int size;
    int top;
    char *arr;//存储括号字符
};
int isEmpty(struct stack *ptr);
int isFull(struct stack *ptr);
void push(struct stack* ptr, char val);
char pop(struct stack* ptr);
int parenthesisMatch(char * exp);
int main()
{
    char *exp = "((8)(*--$$9))";
    if(parenthesisMatch(exp)){
        printf("括号匹配成功");
    }
    else{
        printf("括号匹配失败");
    }
    return 0;
}
 
int isEmpty(struct stack *ptr){
    return ptr->top == -1 ? 1 : 0;
}
 
int isFull(struct stack *ptr){
    return ptr->top == ptr->size -1 ? 1 : 0;
}
 
void push(struct stack* ptr, char val){
    if(isFull(ptr)){
        printf("栈溢出，无法推入元素%c\n", val);
    }
    else{
        ptr->top++;
        ptr->arr[ptr->top] = val;
    }
}
 
char pop(struct stack* ptr){
    if(isEmpty(ptr)){
        printf("栈下溢，无法弹出元素\n");
        return -1;
    }
    else{
        char val = ptr->arr[ptr->top];
        ptr->top--;
        return val;
    }
}
 
int parenthesisMatch(char * exp){
    // 先为栈结构体分配内存，修复野指针问题
    struct stack* sp = (struct stack*)malloc(sizeof(struct stack));
    sp->size = 100;
    sp->top = -1;
    sp->arr = (char *)malloc(sp->size * sizeof(char));

    for (int i = 0; exp[i]!='\0'; i++)
    {
        if(exp[i]=='('){
            push(sp, '(');
        }
        else if(exp[i]==')'){
            if(isEmpty(sp)){
                // 返回前释放内存避免泄漏
                free(sp->arr);
                free(sp);
                return 0;
            }
            pop(sp);
        }
    }
    int result = isEmpty(sp);
    // 释放堆内存
    free(sp->arr);
    free(sp);
    return result;
}

修复验证 #

运行上述代码会输出括号匹配成功，符合测试用例的预期输出。

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