基于链表实现的括号平衡检查函数输出错误问题排查与修正请求

我用链表实现了一个检查表达式括号是否平衡的函数，但不管输入什么表达式，BracketBalancing函数总是返回unbalanced（不平衡）。平衡表达式要求左括号(的数量与右括号)的数量相等且匹配正确。

示例输入输出 #

输入：

Enter the length of the expression for Bracket Balancing
4
Enter the expression for Bracket Balancing
1+()

输出：

This expression is unbalanced

原代码 #

#include <stdio.h>
#include <stdlib.h>
struct LL{
 char data;
 struct LL *next;
};
int isEmpty(struct LL *top){
 if (top == NULL){
 return 1;
 } else{
 return 0;
 }
}
int isFull(struct LL *top){
 struct LL *n = malloc(sizeof(struct LL *));
 if (n == NULL){
 return 1;
 } else{
 return 0;
 }
}
struct LL *push(struct LL *top, char x){
 if (isFull(top)){
 printf("Stack Overflow\n");
 } else{
 struct LL *n = malloc(sizeof(struct LL));
 n->data = x;
 n->next = top;
 top = n;
 }
 return top;
}
struct LL *pop(struct LL *top){
 if (isEmpty(top)){
 printf("Stack Underflow\n");
 } else{
 struct LL *n = malloc(sizeof(struct LL));
 n = top;
 top = top->next;
 free(n);
 }
 return top;
}
int BracketBalancing(char *exp){
 struct LL *top = malloc(sizeof(struct LL));
 top->next = NULL;
 for (int i = 0; exp[i] != '\0'; i++){
 if (exp[i] == '('){
 push(top, exp[i]);
 } else if (exp[i] == ')'){
 if (isEmpty(top)){
 return 0;
 }
 pop(top);
 }
 }
 if (isEmpty(top)){
 return 1;
 } else{
 return 0;
 }
}
int main(int argc, char const *argv[]){
 int n;
 char *expression = (char *)malloc(sizeof(char));
 printf("Enter the length of the expression for Bracket Balancing\n");
 scanf("%d", &n);
 printf("Enter the expression for Bracket Balancing\n");
 for (int i = 0; i < n; i++){
 scanf("%c ", &expression[i]);
 }
 getchar();
 if (BracketBalancing(expression)){
 printf("The expression is balanced\n");
 } else if (!BracketBalancing(expression)){
 printf("This expression is unbalanced\n");
 }
 return 0;
}

问题分析与修复步骤 #

咱们来一步步拆解问题：

1. 栈初始化错误（核心问题）
   在BracketBalancing函数里，你初始化top的时候用malloc创建了一个节点，还设置top->next = NULL——这相当于栈一开始就有一个空节点，而你的isEmpty函数判断的是top == NULL。所以不管怎么操作，最后检查栈是否为空的时候，isEmpty(top)永远返回0，导致函数直接返回0（不平衡）。
   修复：把栈初始化为NULL，而不是malloc一个节点。

2. 表达式内存分配不足
   main里char *expression = (char *)malloc(sizeof(char));只分配了1个字符的空间，但你要存储n个字符的表达式，还需要额外1个位置存字符串终止符'\0'，不然遍历表达式的时候会越界。
   修复：改成char *expression = (char *)malloc(sizeof(char) * (n + 1));

3. 输入读取错误
   scanf("%c ", &expression[i]);里的%c （后面带空格）会自动跳过所有空白字符，导致你实际读取的字符数量会少于n，而且最后没有给表达式加'\0'，BracketBalancing里的循环会读到随机内存。
   修复：改成scanf("%c", &expression[i]);，并且在读取完所有字符后手动加expression[n] = '\0';，同时提前用getchar()吃掉scanf后留下的换行符。

4. pop函数的多余内存分配
   pop函数里struct LL *n = malloc(sizeof(struct LL));是完全多余的，你直接用n = top就可以，malloc的内存没被使用还会造成内存泄漏。
   修复：删掉这个多余的malloc语句。

5. 重复调用平衡检查函数
   main里两次调用BracketBalancing(expression)，第一次调用已经处理了表达式（虽然原代码有问题，但修复后重复调用也没必要），应该把结果存到变量里再判断。
   修复：用一个变量存储检查结果，比如int result = BracketBalancing(expression);，然后根据result判断输出。

修正后的完整代码 #

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

struct LL {
    char data;
    struct LL *next;
};

int isEmpty(struct LL *top) {
    return (top == NULL) ? 1 : 0;
}

int isFull(struct LL *top) {
    struct LL *n = malloc(sizeof(struct LL));
    if (n == NULL) {
        free(n); // 避免内存泄漏
        return 1;
    } else {
        free(n);
        return 0;
    }
}

struct LL *push(struct LL *top, char x) {
    if (isFull(top)) {
        printf("Stack Overflow\n");
        return top;
    } else {
        struct LL *n = malloc(sizeof(struct LL));
        n->data = x;
        n->next = top;
        top = n;
        return top;
    }
}

struct LL *pop(struct LL *top) {
    if (isEmpty(top)) {
        printf("Stack Underflow\n");
        return top;
    } else {
        struct LL *n = top;
        top = top->next;
        free(n);
        return top;
    }
}

int BracketBalancing(char *exp) {
    struct LL *top = NULL; // 正确初始化空栈
    for (int i = 0; exp[i] != '\0'; i++) {
        if (exp[i] == '(') {
            top = push(top, exp[i]);
        } else if (exp[i] == ')') {
            if (isEmpty(top)) {
                return 0; // 遇到右括号但栈为空，直接不平衡
            }
            top = pop(top);
        }
    }
    return isEmpty(top) ? 1 : 0; // 栈空则平衡，否则不平衡
}

int main(int argc, char const *argv[]) {
    int n;
    printf("Enter the length of the expression for Bracket Balancing\n");
    scanf("%d", &n);
    // 分配足够的内存，包含终止符
    char *expression = (char *)malloc(sizeof(char) * (n + 1));
    if (expression == NULL) {
        printf("Memory allocation failed\n");
        return 1;
    }

    printf("Enter the expression for Bracket Balancing\n");
    // 忽略scanf后留下的换行符
    getchar();
    for (int i = 0; i < n; i++) {
        scanf("%c", &expression[i]);
    }
    // 添加字符串终止符
    expression[n] = '\0';

    int result = BracketBalancing(expression);
    if (result) {
        printf("The expression is balanced\n");
    } else {
        printf("This expression is unbalanced\n");
    }

    // 释放分配的内存
    free(expression);
    return 0;
}

现在测试你的示例输入，就能得到正确的"balanced"输出了。

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