链表实现中缀转后缀代码问题：非括号包裹时运算符丢失求助

我是编程初学者，已花费三小时调试基于链表实现的中缀转后缀代码。最初输入带运算符的表达式时无输出，无运算符时可正常输出。修正isOperand参数问题后，仅当整个表达式被括号包裹时代码才正常运行，否则仅输出数字，运算符丢失，恳请帮忙排查原因。

初始代码 #

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

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

struct node *top = NULL;               

void push(char x){
    struct node *temp = (struct node*)malloc(sizeof(struct node));
    temp->data = x;
    temp->next = top;
    top = temp;
}

char pop(){
    struct node *temp = top;
    char op;

    if(top == NULL){
        printf("Stack Empty");
        exit(1);
    }
    op = top->data;
    temp = top;
    top = temp->next;
    free(temp);
    return op;
}

int precedence(char x){
    switch (x){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
    }
    return 0;
}

bool isOperand(char x){
    if(x=='^' || x=='/' || x=='+' || x=='-' || x=='*') return 1;
    else return 0;
}

int main(){
    char x[100];
    char c[100];
    printf("Enter infix expression: \n");
    scanf("%s", c);
    
    int i = 0;
    int j =0;

    while(c[i]){
        if(isOperand){
           if ((precedence(c[i])) >= (precedence(top->data)) || top == NULL || top->data == '('){
                push(c[i]);
            }
            else{
                x[j] = pop();
                j++;
                push(c[i]);
            }
        }
        else if(c[i] == '('){
            push(c[i]);
        }
        else if(c[i] == ')'){
            while(top->data != '('){
                x[j] = pop();
                j++;
            }
            pop();
        }
        else{
            x[j] = c[i];
            j++;
        }
        i++;
    }

    printf("%s", x);
}

修改后代码 #

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

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

struct node *top = NULL;

void push(char x){
    struct node *temp = (struct node*)malloc(sizeof(struct node));
    temp->data = x;
    temp->next = top;
    top = temp;
}

char pop(){
    struct node *temp = top;
    char op;

    if(top == NULL){
        printf("Stack Empty");
        exit(1);
    }
    op = top->data;
    temp = top;
    top = temp->next;
    free(temp);
    return op;
}

int precedence(char x){
    switch (x){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
    }
    return 0;
}

bool isOperand(char x){
    if(x=='^' || x=='/' || x=='+' || x=='-' || x=='*') return 1;
    else return 0;
}

int main(){
    char x[100];
    char c[100];
    printf("Enter infix expression: \n");
    scanf("%s", c);
    
    int i = 0;
    int j = 0;

    while(c[i]){

        if(isOperand(c[i])){
           if (top == NULL || (precedence(c[i])) >= (precedence(top->data)) || top->data == '('){
                push(c[i]);
            }
            else{
                x[j] = pop();
                j++;
                push(c[i]);
            }
        }
        else if(c[i] == '('){
            push(c[i]);
        }
        else if(c[i] == ')'){
            while(top->data != '('){
                x[j] = pop();
                j++;
            }
            pop();
        }
        else{
            x[j] = c[i];
            j++;
        }
        i++;

    }

    printf("%s", x);
}

问题排查与修正方案 #

核心问题1：未处理栈中剩余运算符 #

当表达式遍历完成后，栈内可能还有未弹出的运算符（无括号包裹时，这些运算符不会被触发弹出），这就是无括号时运算符丢失的核心原因。必须在遍历结束后，循环弹出栈中所有剩余运算符，添加到结果字符串中。

核心问题2：结果字符串未加终止符 #

字符数组x作为字符串输出时，必须以'\0'结尾，否则会输出内存中多余的乱码内容。

次要问题：函数命名混淆 #

isOperand函数实际判断的是运算符（operator），不是操作数（operand），命名错误会导致逻辑混淆，建议改为isOperator。

修正后的完整代码 #

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

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

struct node *top = NULL;

void push(char x){
    struct node *temp = (struct node*)malloc(sizeof(struct node));
    temp->data = x;
    temp->next = top;
    top = temp;
}

char pop(){
    struct node *temp = top;
    char op;

    if(top == NULL){
        printf("Stack Empty");
        exit(1);
    }
    op = top->data;
    temp = top;
    top = temp->next;
    free(temp);
    return op;
}

int precedence(char x){
    switch (x){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
    }
    return 0;
}

// 修正函数命名，明确是判断运算符
bool isOperator(char x){
    if(x=='^' || x=='/' || x=='+' || x=='-' || x=='*') return 1;
    else return 0;
}

int main(){
    char x[100];
    char c[100];
    printf("Enter infix expression: \n");
    scanf("%s", c);
    
    int i = 0;
    int j = 0;

    while(c[i]){
        if(isOperator(c[i])){
            // 确保top不为空时再访问top->data，循环弹出高/平优先级运算符
            while(top != NULL && top->data != '(' && precedence(c[i]) <= precedence(top->data)){
                x[j++] = pop();
            }
            push(c[i]);
        }
        else if(c[i] == '('){
            push(c[i]);
        }
        else if(c[i] == ')'){
            while(top->data != '('){
                x[j++] = pop();
            }
            pop(); // 弹出左括号，不加入结果
        }
        else{ // 操作数直接加入结果
            x[j++] = c[i];
        }
        i++;
    }

    // 弹出栈中剩余的所有运算符
    while(top != NULL){
        x[j++] = pop();
    }

    // 添加字符串终止符
    x[j] = '\0';

    printf("Postfix expression: %s\n", x);
    return 0;
}

修正说明 #

1. 添加了遍历结束后弹出栈中剩余运算符的逻辑，确保所有运算符都能加入结果。
2. 给结果字符串x添加了'\0'终止符，避免乱码。
3. 重命名isOperand为isOperator，明确函数功能。
4. 优化了运算符入栈的判断逻辑，用while循环替代单次弹出，处理连续高优先级运算符的情况（比如a+b*c会先弹出*再入栈+）。

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