表达式求值

2026 大纲 三（六）栈、队列和数组的应用（另见《括号匹配》《栈在递归中的应用》《双端队列》）。

三种写法，差别只在运算符的位置

同一个算式有三种写法，区别只有一个：运算符写在两个操作数的前面、中间，还是后面。我们日常用的是中缀，而计算机真正好处理的是后缀。

类型	运算符位置	中缀 `a + b * c` 对应写法	需要括号吗
前缀（波兰式）	操作数前面	`+ a * b c`	不需要
中缀	操作数中间	`a + b * c`	需要，否则无法表达 `(a+b)*c`
后缀（逆波兰式）	操作数后面	`a b c * +`	不需要

🔴 三种写法的操作数顺序完全相同，都是 a b c，变的只有运算符的位置。转换做完先核对一遍操作数序列有没有变——这是最快的自查。

前缀和后缀为什么不需要括号：因为每个运算符的两个操作数在位置上就被唯一确定了。后缀里，一个运算符的操作数就是"它前面最近的两个尚未被消耗的结果"，没有第二种读法；而中缀式里 a + b * c 究竟先算谁，要靠优先级规则或括号才能定下来。

先看一眼

加载可视化中...

转换过程中盯住运算符栈里当时装着什么——真题最爱问的就是"扫描到某个字符时，栈中元素依次是什么"以及"整个过程中栈里最多同时有几个运算符"。

优先级：栈内与栈外

栈外优先数（icp，in-coming priority）：运算符还在输入串里、准备进栈时的优先级；
栈内优先数（isp，in-stack priority）：运算符已经在栈里时的优先级。

读到的运算符 $θ_{2}$ 与栈顶 $θ_{1}$ 比，若 $isp (θ_{1}) \geq icp (θ_{2})$ 就把 $θ_{1}$ 弹出并输出，继续比下一个栈顶；否则 $θ_{2}$ 进栈。

运算符	栈外优先级 icp（进栈时）	栈内优先级 isp（在栈里）
`(`	最高	最低
`*` `/`	高	高
`+` `-`	低	低
`)`	最低（从不进栈）	—

左括号"高进低出"不是矛盾，是两件事：栈外最高保证 ( 一定能进栈；栈内最低保证它不会被任何普通运算符弹出，只有配对的 ) 能把它弹掉。所以 ( 相当于一道墙，墙内的运算符互相比较，永远不会越过这道墙去弹墙外的东西。

中缀转后缀

从左到右扫描，借助一个运算符栈：

遇操作数：直接输出；
遇 (：直接入栈；
遇 )：依次弹出栈顶运算符并输出，直到遇到 (；把 ( 弹出但不输出；
遇普通运算符：把栈中优先级 $\geq$ 当前运算符的依次弹出并输出（遇 ( 就停），然后当前运算符入栈；
扫描结束，把栈中剩余运算符依次弹出并输出。

中缀转后缀的手算逐步表（想跟着走一遍就展开）

把 a + b * c - (d / e) 转换为后缀表达式：

扫描元素	动作	运算符栈（底→顶）	后缀输出
`a`	输出	空	`a`
`+`	栈空，入栈	`+`	`a`
`b`	输出	`+`	`a b`
`*`	栈顶 `+` 优先级 $<$ `*`，不弹；入栈	`+ *`	`a b`
`c`	输出	`+ *`	`a b c`
`-`	弹 `*`（ $\geq$ ）、弹 `+`（ $\geq$ ），入栈	`-`	`a b c * +`
`(`	入栈（栈外优先级最高）	`- (`	`a b c * +`
`d`	输出	`- (`	`a b c * + d`
`/`	栈顶是 `(`，停止弹出；入栈	`- ( /`	`a b c * + d`
`e`	输出	`- ( /`	`a b c * + d e`
`)`	弹 `/` 输出，弹 `(` 不输出	`-`	`a b c * + d e /`
结束	弹 `-`	空	`a b c * + d e / -`

结果：a b c * + d e / -。

上面那张表走完，有两条自查一定要做：① 操作数序列有没有变——a b c d e，与原式一致才对；② 运算符个数对不对——4 个（* + / -），与原式一致。这两条能挡掉绝大多数抄写和漏弹的错误，比重新算一遍快得多。

还有一处细节值得留意：整个过程中 ( 也占着栈里的一个位置。所以题目问"转换过程中栈里最多同时保存几个运算符"时，左括号要一起数进去。

中缀转后缀的参考代码与右括号多余的检查（写代码题时展开）

#include <stdbool.h>
#define MAX_SIZE 100

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

bool isOperand(char ch) {
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')
        || (ch >= '0' && ch <= '9');
}

// 中缀转后缀。infix：输入串；postfix：输出串（调用方保证空间足够）
void infixToPostfix(const char *infix, char *postfix) {
    char stack[MAX_SIZE];
    int top = -1;                   // 运算符栈
    int j = 0;                      // postfix 的写入位置

    for (int i = 0; infix[i] != '\0'; i++) {
        char ch = infix[i];

        if (isOperand(ch)) {
            postfix[j++] = ch;                       // 操作数直接输出
        } else if (ch == '(') {
            stack[++top] = ch;                       // 左括号直接入栈
        } else if (ch == ')') {
            while (top >= 0 && stack[top] != '(')    // 弹到左括号为止
                postfix[j++] = stack[top--];
            if (top >= 0) 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';
}

if (top >= 0) top--; 顺手做了一次《括号匹配》里的"右括号多余"检查：非法串 a) 会让循环因 top < 0 退出，此时若无条件 top--，top 变成 $- 2$ ，后续入栈写到 stack[-1]。

实现时不一定真写两张优先级表。上面的代码用一个 priority() 函数（*// 为 2、 +/- 为 1、( 为 0），并在弹栈循环里加上 stack[top] != '('——与"栈内 ( 最低" 完全等价，且更不容易写错。

`≥` 还是 `>`：一个字决定结合性

第 4 步那个"优先级 $\geq$ 就弹"，看似是个小细节，实际上决定了同优先级运算符的结合方向：

写 ≥：读到 + 时，栈顶的 -（同优先级）会被弹出，于是先输出 -，实现左结合（先算左边）；
写 >：栈顶的 - 不会被弹出，+ 直接压在它上面，最后弹栈时 + 反而先输出——变成先算右边。

拿 a - b + c 做反例，正确结果应是 a b - c +（先算 $a - b$ ）：

扫描	用 `≥`（正确）	用 `>`（错误）
`a`	输出 `a`；栈空	输出 `a`；栈空
`-`	栈空，`-` 入栈；栈 `-`	同左
`b`	输出 `b`；输出串 `a b`	同左
`+`	栈顶 `-` 优先级 $\geq$ `+`，弹出并输出；`+` 入栈	栈顶 `-` 不满足 $>$ ，不弹；`+` 入栈，栈 `- +`
`c`	输出 `c`；输出串 `a b - c`	输出串 `a b c`
结束	弹 `+` → `a b - c +` ✓	弹 `+`、`-` → `a b c + -` ✗

把错误结果 a b c + - 求值：先算 $b + c$ ，再算 $a - (b + c)$ ——与 $(a - b) + c$ 一般不相等（取 $a = 5, b = 3, c = 1$ ：正确 $3$ ，错误 $1$ ）。

🔴 判据是结合性，不是优先级高低。 若表达式含幂运算 ^（右结合， $2^{3^{2}} = 2^{9}$ ），同优先级时不能弹出，条件要写成严格 >。

后缀表达式求值

从左到右扫描，使用一个操作数栈：遇操作数压栈；遇运算符弹出栈顶两个操作数，计算后把结果压回；扫描结束时，栈顶（且是栈中唯一元素）就是结果。

🔴 先弹出的是右操作数，后弹出的才是左操作数。理由很直接：后缀 a b - 表示 $a - b$ ，a 先入栈、b 后入栈，栈内自底向上是 a b，栈顶是 b。弄反的话 5 3 - 会算成 $3 - 5 = - 2$ ——只有减法和除法会暴露这个错误，加法乘法弄反了也看不出来，所以更要在草稿上写清楚。

前缀求值则是它的镜像：从右向左扫描，遇运算符时先弹出的是左操作数。两处的"左右"都指在原中缀表达式中的位置。

后缀与前缀求值的手算逐步表（想跟着走一遍就展开）

后缀求值 3 4 2 * + 5 -：

扫描元素	动作	操作数栈（底→顶）
`3`	入栈	`3`
`4`	入栈	`3 4`
`2`	入栈	`3 4 2`
`*`	弹右 `2`、弹左 `4`，算 $4 \times 2 = 8$ ，压回	`3 8`
`+`	弹右 `8`、弹左 `3`，算 $3 + 8 = 11$ ，压回	`11`
`5`	入栈	`11 5`
`-`	弹右 `5`、弹左 `11`，算 $11 - 5 = 6$ ，压回	`6`

结果 6（对应中缀 $3 + 4 \times 2 - 5$ ✓）。

前缀求值 - + 3 * 4 2 5（对应 $3 + 4 \times 2 - 5$ ），从右往左扫描：

扫描（从右）	动作	栈（底→顶）
`5`	入栈	`5`
`2`	入栈	`5 2`
`4`	入栈	`5 2 4`
`*`	弹左 `4`、弹右 `2`，算 $4 \times 2 = 8$	`5 8`
`3`	入栈	`5 8 3`
`+`	弹左 `3`、弹右 `8`，算 $3 + 8 = 11$	`5 11`
`-`	弹左 `11`、弹右 `5`，算 $11 - 5 = 6$	`6`

结果 6 ✓。

后缀求值的参考代码与三处非法输入检查（写代码题时展开）

#include <ctype.h>
#include <stdbool.h>

// 后缀求值。postfix 中操作数为单个数字字符；ok 返回是否合法
int evalPostfix(const char *postfix, bool *ok) {
    int stack[MAX_SIZE];
    int top = -1;
    *ok = true;

    for (int i = 0; postfix[i] != '\0'; i++) {
        char ch = postfix[i];

        if (isdigit((unsigned char)ch)) {
            if (top == MAX_SIZE - 1) { *ok = false; return 0; }  // 栈满
            stack[++top] = ch - '0';
        } else {
            if (top < 1) { *ok = false; return 0; }  // 不足两个操作数：表达式非法
            int right = stack[top--];                // 先弹出的是右操作数
            int left  = stack[top--];
            int result = 0;
            switch (ch) {
                case '+': result = left + right; break;
                case '-': result = left - right; break;
                case '*': result = left * right; break;
                case '/':
                    if (right == 0) { *ok = false; return 0; }   // 除零
                    result = left / right; break;
                default:  *ok = false; return 0;                 // 非法字符
            }
            stack[++top] = result;
        }
    }
    if (top != 0) { *ok = false; return 0; }   // 结束时栈中应恰好剩 1 个结果
    return stack[top];
}

if (top < 1) 是本篇的边界重点：以非法输入 3 + 为例——3 入栈后 top = 0，读到 + 时若不检查就连弹两次：第一次 right = 3（top 变 $- 1$ ），第二次读 stack[-1]， 越界读，且 top 变成 $- 2$ 。 结束时 top != 0 也要判：输入 3 4 扫描完栈里有两个数，说明运算符不够，同样非法。

三处边界值得单独记一下，它们是同一件事的三种表现：遇运算符时操作数不足两个、遇 ) 时找不到 (、扫描结束时栈中剩余元素个数不对。三者都在说"表达式本身不合法"。

另一套算法：中缀直接求值（双栈）（题面不给后缀式时展开）

不先转后缀，而是一趟扫描同时维护两个栈——运算符栈与操作数栈。规则与中缀转后缀完全一致，只是"输出运算符"改成"立刻用它算一次"。

// 把栈顶两个操作数按 op 算一次，结果压回
static bool reduce(int *num, int *numTop, char op) {
    if (*numTop < 1) return false;
    int right = num[(*numTop)--];
    int left  = num[(*numTop)--];
    int res;
    switch (op) {
        case '+': res = left + right; break;
        case '-': res = left - right; break;
        case '*': res = left * right; break;
        case '/': if (right == 0) return false; res = left / right; break;
        default:  return false;
    }
    num[++(*numTop)] = res;
    return true;
}

int evalInfix(const char *s, bool *ok) {
    int  num[MAX_SIZE]; int numTop = -1;   // 操作数栈
    char op [MAX_SIZE]; int opTop  = -1;   // 运算符栈
    *ok = true;

    for (int i = 0; s[i] != '\0'; i++) {
        char ch = s[i];
        if (isdigit((unsigned char)ch)) {
            num[++numTop] = ch - '0';
        } else if (ch == '(') {
            op[++opTop] = ch;
        } else if (ch == ')') {
            while (opTop >= 0 && op[opTop] != '(')
                if (!reduce(num, &numTop, op[opTop--])) { *ok = false; return 0; }
            if (opTop < 0) { *ok = false; return 0; }   // 右括号多余
            opTop--;                                    // 弹出 '('
        } else {
            while (opTop >= 0 && op[opTop] != '(' &&
                   priority(op[opTop]) >= priority(ch))
                if (!reduce(num, &numTop, op[opTop--])) { *ok = false; return 0; }
            op[++opTop] = ch;
        }
    }
    while (opTop >= 0) {
        if (op[opTop] == '(') { *ok = false; return 0; }  // 左括号多余
        if (!reduce(num, &numTop, op[opTop--])) { *ok = false; return 0; }
    }
    if (numTop != 0) { *ok = false; return 0; }
    return num[numTop];
}

与"先转后缀再求值"的区别只有一处：那边把运算符写到输出串，这边立刻拿去算。两者扫描逻辑逐字对应，所以只要掌握了中缀转后缀，双栈直接求值就是免费的。

表达式树：三种写法的统一解释

把表达式画成二叉树：叶结点是操作数，分支结点是运算符，每个运算符的左右子树就是它的左右操作数。a + b * c 的表达式树：

text

遍历方式	结果	对应
先序（根左右）	`+ a * b c`	前缀表达式
中序（左根右）	`a + b * c`	中缀表达式
后序（左右根）	`a b c * +`	后缀表达式

这个对应关系一口气解释了本篇的全部结论：前缀/后缀不需要括号，是因为树结构已经把运算顺序固定了，先序/后序遍历能唯一还原这棵树；中缀需要括号，是因为中序遍历会丢掉结构信息——不加括号时 (a+b)*c 与 a+b*c 的中序序列可能相同，光靠中序无法唯一确定一棵树（这与"仅由中序序列不能唯一确定二叉树"是同一件事）；而三种表达式的操作数出现顺序都一样，是因为三种遍历访问叶结点的相对次序相同。

四种算法的复杂度来历（想知道为什么不能说"每步常数"就展开）

算法	时间复杂度	来历
中缀转后缀	$O (n)$	每个字符扫描一次；每个运算符最多入栈一次、出栈一次，入出栈均 $O (1)$ ，总操作数 $\leq 3 n$
后缀求值	$O (n)$	单趟扫描；每个操作数入栈一次，每个运算符触发两次弹栈一次入栈，均摊 $O (1)$
前缀求值	$O (n)$	同后缀，只是扫描方向相反
中缀直接求值	$O (n)$	两个栈各自的总入出栈次数仍与 $n$ 同阶

空间复杂度均为 $O (n)$ ：

中缀转后缀：运算符栈最大深度 $=$ 最大括号嵌套层数 $+$ 连续未结算的运算符数，最坏 $O (n)$ ；
后缀求值：操作数栈最大深度出现在"操作数连续入栈"时，最坏 $O (n)$ （如 1 2 3 4 ... n + + ... +）。

均摊分析的说法：不能说"每个字符 $O (1)$ "就完事——遇到一个运算符时可能连续弹出好几个。正确的论证是：每个运算符一生只会被弹出一次，所以整个过程的弹栈总次数不超过运算符个数，摊到 $n$ 个字符上仍是 $O (n)$ 。这种"总量有界"的论证方式在后面的图算法里还会用到。

考点速记

三条会被反复调用的结论：

≥ 保证左结合，改成 > 会把 a-b+c 算成 a-(b+c)；判据是结合性，不是优先级高低。
后缀先弹右、前缀先弹左，只有减法除法才会暴露顺序错误。
三种表达式 = 表达式树的三种遍历，中缀丢掉括号后不能唯一还原树。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：几乎全部围绕中缀转后缀的过程状态，而不是结果本身：

扫描到某个字符时，运算符栈里依次是什么：题面给出中缀式和一个位置（如"扫描到 f 时"），要你写出栈内元素。做法是老老实实按五条规则走到那一步，把栈画出来——注意题目问的次序通常是栈底到栈顶。
转换过程中栈里最多同时保存几个运算符：走完整个过程，记录栈的最高水位。这与括号匹配里"栈的最大深度"是同一类问题，只是这里栈里除了 ( 还有普通运算符。
求某个中缀式的等价后缀式：四个选项里常有"操作数顺序被打乱"的干扰项，先用"操作数序列不变"这一条筛掉一半。
给定双栈的操作规则，问若干次运算后栈顶是什么：题面自定义一个函数（比如"从操作数栈弹 $a$ 、 $b$ ，从运算符栈弹 $o p$ ，算 $b o p a$ 再压回"），要你模拟几轮。关键是照抄题面的操作数顺序——它明确写了算 $b o p a$ ，就不要按自己习惯的"先弹是右操作数"去套。

易错：弹栈条件写成 >。 会把左结合的减法算成右结合，a-b+c 变成 a-(b+c)。

易错：后缀求值时把左右操作数弄反。 先弹的是右操作数；减除才暴露。

易错：答栈内元素时次序反了。 看清题目问的是"栈底到栈顶"还是"栈顶到栈底"。

易错：忘了 ( 也占栈里的位置。 问"栈中最多有几个运算符"时，左括号要算进去。

教材出处

表达式求值作为栈的经典应用（案例 3.3 表达式求值）：严蔚敏《数据结构（C 语言版）》（第 2 版）p56「3.1 栈和队列的定义和特点 · 案例引入」
括号匹配中"栈顶最急迫的期待得以消解"的机制（本篇处理 ) 时"弹到 ( 为止"与之同源）：同书 p56
顺序栈的入栈、出栈算法（本篇两个栈的底层操作）：同书 p58–p59

真题练习

2026Q4210分 2025Q22分 2024Q22分 2020Q22分 2018Q12分 2017Q22分 2015Q12分 2014Q22分 2013Q22分 2012Q22分 2010Q12分 2009Q22分

表达式求值

三种写法，差别只在运算符的位置

先看一眼

优先级：栈内与栈外

中缀转后缀

`≥` 还是 `>`：一个字决定结合性

后缀表达式求值

表达式树：三种写法的统一解释

考点速记

相关知识

相关文章

交互体验

真题练习

相关真题（12题）

表达式求值 ​

三种写法，差别只在运算符的位置 ​

先看一眼 ​

优先级：栈内与栈外 ​

中缀转后缀 ​

≥ 还是 >：一个字决定结合性 ​

后缀表达式求值 ​

表达式树：三种写法的统一解释 ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

相关真题（12题）

表达式求值

三种写法，差别只在运算符的位置

先看一眼

优先级：栈内与栈外

中缀转后缀

`≥` 还是 `>`：一个字决定结合性

后缀表达式求值

表达式树：三种写法的统一解释

考点速记

相关知识

真题练习