中缀转后缀C语言代码异常：输入指定表达式输出缺失乘号

问题描述 #

输入表达式a+(b-c)*d$e/f+g$(h-i)时，代码输出结果为abc-de$f/ghi-$+，但正确的后缀表达式应为abc-de^*f/+ghi-^+，输出缺失了一个乘号*，以下是问题排查及修正方案：

原代码 #

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n;
int stackfull(int top)
{
    if(top==n)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int stackempty(int top)
{
    if(top==-1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int push(char stack[],int top,int data)
{
    if(!stackfull(top))
    {
        top+=1;
        stack[top]=data;
    
    }
    else
    {
        printf("Stack full!");
    }
}
int pop(char stack[],int top)
{
    if(!stackempty(top))
    {
        char data=stack[top];
        top--;
        return data;
    }
    /*else
    {
        printf("Stack empty!");
    }*/
}
void getstr(char a[])
{
    for(int i=0;i<70;i++)
    {
        char c;
        scanf("%c",&c);
        if(c=='\n')
        {
            a[i]='\0';
            break;
        }
        else{
            a[i]=c;
        }
    }
}
int operator(char o)
{
    int r=0;
    if(o=='+'||o=='-'||o=='*'||o=='/'||o=='$')
    {
        r=1;
    }
    return r;
}
int priority(char o)
{
    int r;
    switch(o)
    {
        case '+': r= 1;
        break;
        case '-': r= 1;
        break;
        case '*': r= 2;
        break;
        case '/': r= 2;
        break;
        case '$': r= 3;
    }
    return r;
}
int intopost(char a[],char out[])
{
    int i=0,j=0,top=-1;
    char stk[n];
    while(a[i]!='\0')
    {
        if(operator(a[i]))
        {
            if(stackempty(top))
            {
                push(stk,top,a[i]);
                top++;
            }
            else
            {
                if(stk[top]=='('||priority(a[i])>priority(stk[top]))
                {
                    printf("\t2=%s %s\t",stk,out);
                    push(stk,top,a[i]);
                    top++;
                }
                else if(priority(a[i])<priority(stk[top])||priority(a[i])==priority(stk[top]))
                {
                    printf("\t2=%s %s\t",stk,out);
                    out[j]=pop(stk,top);
                    top--;
                    j++;
                    push(stk,top,a[i]);
                    top++;
                }
            }
        }
        else if(a[i]=='(')
        {
                push(stk,top,a[i]);
                top++;
            }
        else if(a[i]==')')
        {
                while (stk[top]!='(')
                {
                    if(stackempty(top)&&stk[top]=='(')
                    {
                        return -1;
                    }
                    else
                    {    
                        out[j] = pop(stk,top);
                        j++;
                    }
                    top--;
                }
                char ch=pop(stk,top);
                top--;
            }
        else if((a[i]>='a'&&a[i]<='z')||(a[i]>='A'&&a[i]<='Z'))
        {
            out[j]=a[i];
            j++;
        }
        i++;
    }
    while(stackempty(top));
    {
        out[j]=pop(stk,top);
        j++;
        top--;
    }
    if(!stackempty(top))
    {
        out[j]=pop(stk,top);
        j++;
        top--;
    }
    
    out[j]='\0';
    j++;
}
int main()
{
    char s[70],o[70],ch;
    int i,f; 
    printf("Enter the expression:");
    getstr(s);
    printf("%s -> ",s);
    n=strlen(s);
    intopost(s,o);
    printf("%s",o);
}

核心问题分析 #

1. push函数逻辑错误 #

push函数声明返回int，但未返回更新后的top值，函数内修改的是局部变量top，外部的top不会同步更新。后续手动执行top++属于错误的补偿操作，导致栈的状态跟踪完全混乱，这是丢失运算符的主要原因之一。

2. 运算符优先级处理不彻底 #

当遇到优先级小于等于栈顶运算符的情况时，代码仅弹出一个栈顶运算符就压入新运算符，但正确逻辑应该是循环弹出所有优先级大于等于当前运算符的栈顶元素（直到栈空、遇到左括号或栈顶运算符优先级更低）。

3. 栈清空阶段语法错误 #

while(stackempty(top));末尾多了分号，导致循环体为空，直接跳过栈元素弹出逻辑。后续的if判断也只能处理一个剩余元素，无法清空栈中所有剩余运算符，导致*这类运算符留在栈中未输出。

4. 右括号处理的越界风险 #

if(stackempty(top)&&stk[top]=='(')中，栈空时stk[top]（即stk[-1]）属于数组越界访问，逻辑完全错误。

修正后的代码 #

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n;

int stackfull(int top) {
    return top == n;
}

int stackempty(int top) {
    return top == -1;
}

// 修改push函数：返回更新后的top
int push(char stack[], int top, char data) {
    if (!stackfull(top)) {
        top++;
        stack[top] = data;
    } else {
        printf("Stack full!");
    }
    return top;
}

// 修改pop函数：通过指针更新top
char pop(char stack[], int *top) {
    char data = '\0';
    if (!stackempty(*top)) {
        data = stack[*top];
        (*top)--;
    } else {
        printf("Stack empty!");
    }
    return data;
}

void getstr(char a[]) {
    int i = 0;
    char c;
    while ((c = getchar()) != '\n' && i < 69) {
        a[i++] = c;
    }
    a[i] = '\0';
}

int is_operator(char o) {
    return (o == '+' || o == '-' || o == '*' || o == '/' || o == '$');
}

int priority(char o) {
    switch(o) {
        case '+':
        case '-': return 1;
        case '*':
        case '/': return 2;
        case '$': return 3;
        default: return 0;
    }
}

void intopost(char a[], char out[]) {
    int i = 0, j = 0, top = -1;
    char stk[n];
    while (a[i] != '\0') {
        if (is_operator(a[i])) {
            // 循环处理所有优先级>=当前运算符的栈顶元素
            while (!stackempty(top) && stk[top] != '(' && priority(a[i]) <= priority(stk[top])) {
                out[j++] = pop(stk, &top);
            }
            top = push(stk, top, a[i]);
        } else if (a[i] == '(') {
            top = push(stk, top, a[i]);
        } else if (a[i] == ')') {
            // 弹出直到左括号
            while (!stackempty(top) && stk[top] != '(') {
                out[j++] = pop(stk, &top);
            }
            if (!stackempty(top)) {
                pop(stk, &top); // 弹出左括号，不输出
            } else {
                printf("Mismatched parentheses!");
                return;
            }
        } else if ((a[i] >= 'a' && a[i] <= 'z') || (a[i] >= 'A' && a[i] <= 'Z')) {
            out[j++] = a[i];
        }
        i++;
    }
    // 弹出栈中所有剩余运算符
    while (!stackempty(top)) {
        out[j++] = pop(stk, &top);
    }
    out[j] = '\0';
}

int main() {
    char s[70], o[70];
    printf("Enter the expression:");
    getstr(s);
    printf("%s -> ", s);
    n = strlen(s);
    intopost(s, o);
    printf("%s\n", o);
    return 0;
}

修正说明 #

1. 重写push和pop函数：push返回更新后的top，pop通过指针直接修改外部top，确保栈状态跟踪准确。
2. 修复运算符处理逻辑：循环弹出所有符合条件的栈顶运算符，保证优先级规则正确执行。
3. 修正栈清空循环：移除多余分号，循环弹出所有剩余运算符。
4. 修复右括号处理：移除越界判断，确保括号匹配逻辑安全。
5. 函数名优化：将operator改为is_operator，避免与C关键字冲突。

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