中缀表达式转后缀：栈处理优先级

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。中缀转后缀和逆波兰求值是「栈的应用」这一考点里配套的一对题，一个把中缀「翻译」成后缀，一个把后缀「求值」；两道题共用一套栈的直觉，但翻译这一步的坑更多。它是经典训练题，不是真题，也不押题。

题目

给定一个只含单字符操作数（a–z、A–Z、0–9）、四则运算符 + - * / 和圆括号的合法中缀表达式字符串，将其转换为等价的后缀表达式字符串。例如 a+b*c-(d/e) 应转换为 abc*+de/-。

这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——直白写法就是最优解，力气花在把优先级比较和括号处理写准上。

直观解法：一个运算符栈,一趟扫描

中缀表达式里运算符的书写顺序和运算顺序不一致（* 写在 + 后面却要先算），后缀表达式没有这个问题。转换的核心是用一个运算符栈「暂存」还不能确定输出顺序的运算符，只有当确定某个运算符不会被后面出现的更高优先级运算符打断时，才把它弹出输出。

#include <ctype.h>

int priority(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

// infix: 输入的中缀表达式字符串
// postfix: 输出的后缀表达式字符串（调用方保证空间足够）
void infixToPostfix(char *infix, char *postfix) {
    char stack[MAX_SIZE];
    int top = -1;
    int j = 0;

    for (int i = 0; infix[i] != '\0'; i++) {
        char ch = infix[i];
        if (isalnum(ch)) {
            postfix[j++] = ch;                  // 操作数：直接输出
        } else if (ch == '(') {
            stack[++top] = ch;                  // 左括号：直接入栈
        } else if (ch == ')') {
            // 右括号：弹出并输出，直到遇到左括号
            while (top >= 0 && stack[top] != '(')
                postfix[j++] = stack[top--];
            top--;                              // 弹出左括号本身（不输出）
        } else {
            // 普通运算符：弹出栈中优先级 >= 当前运算符的，直到遇到左括号或栈空
            while (top >= 0 && stack[top] != '(' &&
                   priority(stack[top]) >= priority(ch))
                postfix[j++] = stack[top--];
            stack[++top] = ch;
        }
    }
    while (top >= 0)                            // 扫描结束，弹出栈中剩余运算符
        postfix[j++] = stack[top--];
    postfix[j] = '\0';
}

拿 a+b*c-(d/e) 走一遍：a 输出；+ 入栈；b 输出；* 优先级高于栈顶 +，入栈；c 输出；- 到来时先弹出优先级 ≥ 它的 *、+ 并输出，再把自己入栈；( 直接入栈；d 输出；/ 入栈（( 挡着，不会被弹）；e 输出；) 弹出 / 并输出，再弹出 ( 丢弃；扫描结束，弹出剩下的 -。最终输出 abc*+de/-。

复杂度：扫描字符串一遍，每个字符至多入栈出栈各一次，时间 $O (n)$ ；运算符栈最多存 n 个字符，空间 $O (n)$ 。

为什么它就是满分解

用总纲的「找浪费三问」审一遍，三问全部答「没有」：

有没有重复扫描？ 没有。每个字符只读一次，该输出就输出、该入栈就入栈，不回头重新扫描已处理过的部分。
有没有重算已知的东西？ 没有。栈顶就是「当前还没决定输出时机的、优先级最高的待处理运算符」，需要比较时直接看栈顶，不用重新遍历找。
有没有放着性质不用？ 没有。运算符优先级这一性质正好靠栈的「后进先出 + 弹出条件」直接承载：高优先级的运算符会被压在更早入栈的低优先级运算符之上,等它先被消费。

更根本的一条：转换至少要把每个字符看一遍——读一遍字符串就是 $O (n)$ 的下界，任何正确算法都躲不开。碰到下界，就没有优化空间，直观写法即最优。

真正的难点在优先级比较和括号处理

分不在优化上,在两处容易翻车的地方：

弹出条件必须是「优先级 ≥ 当前运算符」，不能改成「>」。如果改成严格大于，相同优先级的运算符不会被弹出，会破坏左结合性。例如 a-b+c 应该先算 a-b，如果 + 不弹出同优先级的 -，栈里会变成 - +，最终输出错误的顺序，等价于先算 b+c。这是本题最高频的失分点。
左括号「入栈前」和「入栈后」的优先级不是一回事。( 入栈时不看任何优先级比较，直接压栈；入栈之后，它在弹出条件的比较里要被当成「优先级最低」处理（while 条件里专门用 stack[top] != '(' 挡住普通运算符），这样才能保证只有配对的 ) 才能把它弹出，普通运算符不会越过左括号去弹栈里更早的运算符。
右括号只负责清空到左括号为止，左括号本身不输出。) 出现时要连续弹出直到碰到 (，然后把这个 ( 也弹出但不写进后缀表达式——括号在后缀表达式里本来就没有存在的意义，它们只是中缀表达式里用来标记优先级的辅助符号。
扫描结束后要把栈清空。字符串读完了不代表转换完了，栈里可能还压着若干运算符（比如例子里最后剩的 -），必须依次弹出追加到输出末尾。

一个运算符栈一趟扫描,看一遍

用 a+b*c-(d/e) 演示——注意 - 到来时一次性弹出 * 和 +（体现优先级 ≥ 的弹出条件），以及 ( 如何挡住 / 不被外面的运算符提前弹出：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足

这道题结构简单,过度设计的空间不大,但有两个常见的「想复杂了」：

想同时维护操作数栈和运算符栈直接算出结果。中缀直接求值确实需要双栈，但这道题只要求「转换成后缀表达式字符串」，不要求求值——只需要一个运算符栈来决定输出顺序，操作数看到就立即输出，不需要额外的操作数栈。
想给不同优先级设计更复杂的数据结构（比如优先级队列）。运算符种类和优先级层级都很少（本题只有两档），一个 priority() 函数配合栈的弹出条件已经把优先级规则表达清楚了，没必要引入额外结构。

下一步

看栈处理表达式转换的交互演示：表达式求值可视化
同属「栈的应用」的拓展题：括号匹配、逆波兰表达式求值
回到方法论源头：「暴力解到最优解」真题专题总纲

中缀表达式转后缀：栈处理优先级 ​

题目 ​

直观解法：一个运算符栈,一趟扫描 ​

为什么它就是满分解 ​

真正的难点在优先级比较和括号处理 ​

一个运算符栈一趟扫描,看一遍 ​

别画蛇添足 ​

下一步 ​