表达式求值与二叉树遍历教程

本文从零讲解中缀、前缀、后缀三种表达式，以及它们与二叉树三种遍历的对应关系，并给出双栈法、调度场算法、后缀/前缀求值等经典算法。全文用一个例子贯穿：

1
中缀：3 + 4 * 2 / (1 - 5)^2
2
后缀：3 4 2 * 1 5 - 2 ^ / +
3
前缀：+ 3 / * 4 2 ^ - 1 5 2

最终结果都是 3.5。

1. 三种表达式是什么#

1.1 中缀表达式#

人最熟悉的写法，运算符在两个操作数中间：

1
3 + 4 * 2

特点：有优先级、有括号，计算机直接求值麻烦。

1.2 后缀表达式（逆波兰式 RPN）#

运算符在操作数后面：

1
3 4 2 * +

特点：没有括号，运算顺序唯一，计算机最容易求值。

1.3 前缀表达式（波兰式 PN）#

运算符在操作数前面：

1
+ 3 * 4 2

特点：同样没有括号，求值时从右往左扫描即可。

2. 表达式树：三种表达式的统一来源#

任何中缀表达式都可以画成一棵二叉树：

叶子节点：数字
内部节点：运算符
左子树、右子树：参与运算的子表达式

以 3 + 4 * 2 / (1 - 5)^2 为例，表达式树为：

2.1 三种遍历对应三种表达式#

遍历方式	顺序	得到的表达式	例子
前序遍历	根 → 左 → 右	前缀表达式 PN	`+ 3 / * 4 2 ^ - 1 5 2`
中序遍历	左 → 根 → 右	中缀表达式（需补括号）	`3 + 4 * 2 / (1 - 5)^2`
后序遍历	左 → 右 → 根	后缀表达式 RPN	`3 4 2 * 1 5 - 2 ^ / +`

一句话总结：同一棵表达式树，三种遍历顺序，得到三种表达式。

3. 中缀表达式求值：双栈法#

双栈法直接扫描中缀表达式，一边读一边算。

3.1 规则#

一个数字栈 num，一个运算符栈 op
从左到右扫描
遇到数字 → 压 num
遇到左括号 → 压 op
遇到右括号 → 弹 op 直到左括号，每弹一个运算符就算一次
遇到运算符 → 比较优先级：
- 栈顶优先级高于当前，或 同级且当前不是 ^，就弹栈顶计算
- 否则当前运算符入 op
扫描完，把 op 里剩下的全部弹出算完

3.2 模拟 `3 + 4 * 2 / (1 - 5)^2`#

步骤	读到	动作	num 栈	op 栈
1	`3`	数字入栈	`[3]`	`[]`
2	`+`	入栈	`[3]`	`[+]`
3	`4`	数字入栈	`[3,4]`	`[+]`
4	`*`	`+` 优先级低，不弹；`*` 入栈	`[3,4]`	`[+,*]`
5	`2`	数字入栈	`[3,4,2]`	`[+,*]`
6	`/`	弹 `` 算 `42=8`；`+` 低不弹；`/` 入栈	`[3,8]`	`[+,/]`
7	`(`	入栈	`[3,8]`	`[+,/,(]`
8	`1`	数字入栈	`[3,8,1]`	`[+,/,(]`
9	`-`	栈顶是 `(`，不弹；`-` 入栈	`[3,8,1]`	`[+,/,(,-]`
10	`5`	数字入栈	`[3,8,1,5]`	`[+,/,(,-]`
11	`)`	弹 `-` 算 `1-5=-4`；遇 `(` 弹掉	`[3,8,-4]`	`[+,/]`
12	`^`	`/` 优先级低，不弹；`^` 入栈	`[3,8,-4]`	`[+,/,^]`
13	`2`	数字入栈	`[3,8,-4,2]`	`[+,/,^]`
14	结束	弹 `^` 算 `(-4)^2=16`	`[3,8,16]`	`[+,/]`
15	结束	弹 `/` 算 `8/16=0.5`	`[3,0.5]`	`[+]`
16	结束	弹 `+` 算 `3+0.5=3.5`	`[3.5]`	`[]`

结果 3.5。

3.3 双栈法与后序遍历的关系#

双栈法每次弹栈计算，相当于在表达式树中合并一棵小子树：

num 栈存的是已经算完的子树结果
op 栈存的是还没轮到算的子树根
弹出一个运算符，就表示它的左右子树都已完成，可以访问这个根

所以：

双栈法 = 一边隐式建表达式树，一边做后序遍历求值。

4. 中缀转后缀：调度场算法#

调度场算法由 Dijkstra 提出，专门用来把中缀转成后缀。

4.1 规则#

准备一个输出队列和一个运算符栈：

遇到数字 → 加入输出队列
遇到左括号 → 压入运算符栈
遇到右括号 → 不断弹出运算符栈顶加入输出队列，直到遇到左括号，然后把左括号弹掉
遇到运算符 →
- 只要栈不空，且栈顶不是左括号，且栈顶优先级高于当前，或 同级且当前是左结合，就弹出栈顶加入输出
- 然后把当前运算符压入栈
扫描结束 → 把运算符栈里剩下的全部弹出加入输出

4.2 模拟 `3 + 4 * 2 / (1 - 5)^2`#

步骤	读到	动作	输出队列	运算符栈
1	`3`	数字输出	`3`	`[]`
2	`+`	压栈	`3`	`[+]`
3	`4`	数字输出	`3 4`	`[+]`
4	`*`	`+` 低，不弹；压 `*`	`3 4`	`[+,*]`
5	`2`	数字输出	`3 4 2`	`[+,*]`
6	`/`	弹 `*` 输出；`+` 低不弹；压 `/`	`3 4 2 *`	`[+,/]`
7	`(`	压栈	`3 4 2 *`	`[+,/,(]`
8	`1`	数字输出	`3 4 2 * 1`	`[+,/,(]`
9	`-`	栈顶是 `(`，不弹；压 `-`	`3 4 2 * 1`	`[+,/,(,-]`
10	`5`	数字输出	`3 4 2 * 1 5`	`[+,/,(,-]`
11	`)`	弹 `-` 输出；弹掉 `(`	`3 4 2 * 1 5 -`	`[+,/]`
12	`^`	`/` 低，不弹；压 `^`	`3 4 2 * 1 5 -`	`[+,/,^]`
13	`2`	数字输出	`3 4 2 * 1 5 - 2`	`[+,/,^]`
14	结束	弹 `^`、`/`、`+`	`3 4 2 * 1 5 - 2 ^ / +`	`[]`

得到后缀表达式：

1
3 4 2 * 1 5 - 2 ^ / +

5. 后缀表达式求值#

后缀求值只需要一个数字栈。

5.1 规则#

从左到右扫描
遇到数字 → 压栈
遇到运算符 → 弹出两个数：
- 先弹出的是 右操作数 b
- 后弹出的是 左操作数 a
- 计算 a op b，结果压回栈
最后栈里只剩一个数，就是结果

5.2 模拟 `3 4 2 * 1 5 - 2 ^ / +`#

步骤	读到	动作	栈
1	`3`	压栈	`[3]`
2	`4`	压栈	`[3,4]`
3	`2`	压栈	`[3,4,2]`
4	`*`	弹 `b=2, a=4`，算 `4*2=8`	`[3,8]`
5	`1`	压栈	`[3,8,1]`
6	`5`	压栈	`[3,8,1,5]`
7	`-`	弹 `b=5, a=1`，算 `1-5=-4`	`[3,8,-4]`
8	`2`	压栈	`[3,8,-4,2]`
9	`^`	弹 `b=2, a=-4`，算 `(-4)^2=16`	`[3,8,16]`
10	`/`	弹 `b=16, a=8`，算 `8/16=0.5`	`[3,0.5]`
11	`+`	弹 `b=0.5, a=3`，算 `3+0.5=3.5`	`[3.5]`

结果 3.5。

6. 前缀表达式求值#

前缀求值同样一个数字栈，但 从右往左扫描。

6.1 规则#

从右到左扫描
遇到数字 → 压栈
遇到运算符 → 弹出两个数：
- 先弹出的是 左操作数 a
- 后弹出的是 右操作数 b
- 计算 a op b，结果压回栈
最后栈里只剩一个数，就是结果

6.2 模拟 `+ 3 / * 4 2 ^ - 1 5 2`#

从右往左读的顺序是：

1
2 5 1 - ^ 2 4 * / 3 +

步骤	读到	动作	栈
1	`2`	压栈	`[2]`
2	`5`	压栈	`[2,5]`
3	`1`	压栈	`[2,5,1]`
4	`-`	弹 `a=1, b=5`，算 `1-5=-4`	`[2,-4]`
5	`^`	弹 `a=-4, b=2`，算 `(-4)^2=16`	`[16]`
6	`2`	压栈	`[16,2]`
7	`4`	压栈	`[16,2,4]`
8	`*`	弹 `a=4, b=2`，算 `4*2=8`	`[16,8]`
9	`/`	弹 `a=8, b=16`，算 `8/16=0.5`	`[0.5]`
10	`3`	压栈	`[0.5,3]`
11	`+`	弹 `a=3, b=0.5`，算 `3+0.5=3.5`	`[3.5]`

结果 3.5。

7. 三种求值方法对比#

表达式	扫描方向	栈的数量	弹栈顺序	需要优先级	需要括号
中缀	左 → 右	两个栈（数字 + 运算符）	先右后左	需要	需要
后缀	左 → 右	一个数字栈	先右后左	不需要	不需要
前缀	右 → 左	一个数字栈	先左后右	不需要	不需要

记忆口诀：

中缀双栈比优先，后缀从左先弹右，前缀从右先弹左。

8. 递归下降求值（扩展）#

递归下降是编译器前端常用的方法，按文法递归解析。

文法示例：

1
expr   -> term { (+ | -) term }
2
term   -> factor { (* | /) factor }
3
factor -> number | '(' expr ')' | '-' factor

代码框架：

1
double parseExpr(string& s) {
2
    double val = parseTerm(s);
3
    while (pos < s.size() && (s[pos] == '+' || s[pos] == '-')) {
4
        char op = s[pos++];
5
        double rhs = parseTerm(s);
6
        if (op == '+') val += rhs;
7
        else val -= rhs;
8
    }
9
    return val;
10
}
11

12
double parseTerm(string& s) {
13
    double val = parseFactor(s);
14
    while (pos < s.size() && (s[pos] == '*' || s[pos] == '/')) {
15
        char op = s[pos++];
16
        double rhs = parseFactor(s);
17
        if (op == '*') val *= rhs;
18
        else val /= rhs;
19
    }
20
    return val;
21
}
22

23
double parseFactor(string& s) {
24
    if (s[pos] == '(') {
25
        pos++;
26
        double val = parseExpr(s);
27
        pos++;
28
        return val;
29
    }
30
    if (s[pos] == '-') {
31
        pos++;
32
        return -parseFactor(s);
33
    }
34
    double val = 0;
35
    while (pos < s.size() && isdigit(s[pos])) {
36
        val = val * 10 + (s[pos] - '0');
37
        pos++;
38
    }
39
    return val;
40
}

特点：结构清晰，易扩展，但需要处理左递归。

9. 总结#

中缀表达式：人熟悉，计算机麻烦，用双栈法求值。
后缀表达式：一个栈，从左到右，先弹右后弹左。
前缀表达式：一个栈，从右到左，先弹左后弹右。
表达式树：三种遍历对应三种表达式。
- 前序 → 前缀
- 中序 → 中缀
- 后序 → 后缀
双栈法：本质是隐式建树 + 后序遍历求值。
调度场算法：中缀转后缀的标准算法。

10. 推荐练习#

408 真题：2014 年中缀转后缀、2025 年后缀求值入栈次数、括号匹配。
LeetCode：150（逆波兰表达式求值）、224（基本计算器）、227（基本计算器 II）、772（基本计算器 III）、1597（构造二叉表达式树）。
考研机试：上海交通大学 KY102、天津大学 2025 机试、浙大复试机试。
参考书：王道《数据结构考研复习指导》第 3 章栈和队列；《算法竞赛入门经典》表达式求值章节；OI-wiki 表达式求值页面。

本文可作为表达式求值专题的教程笔记，配合代码实践和手写模拟，效果更佳。

AKira Lau

1. 三种表达式是什么#

1.1 中缀表达式#

1.2 后缀表达式（逆波兰式 RPN）#

1.3 前缀表达式（波兰式 PN）#

2. 表达式树：三种表达式的统一来源#

2.1 三种遍历对应三种表达式#

3. 中缀表达式求值：双栈法#

3.1 规则#

3.2 模拟 `3 + 4 * 2 / (1 - 5)^2`#

3.3 双栈法与后序遍历的关系#

4. 中缀转后缀：调度场算法#

4.1 规则#

4.2 模拟 `3 + 4 * 2 / (1 - 5)^2`#

5. 后缀表达式求值#

5.1 规则#

5.2 模拟 `3 4 2 * 1 5 - 2 ^ / +`#

6. 前缀表达式求值#

6.1 规则#

6.2 模拟 `+ 3 / * 4 2 ^ - 1 5 2`#

7. 三种求值方法对比#

8. 递归下降求值（扩展）#

9. 总结#

10. 推荐练习#

继续阅读

AKira Lau

1. 三种表达式是什么#

1.1 中缀表达式#

1.2 后缀表达式（逆波兰式 RPN）#

1.3 前缀表达式（波兰式 PN）#

2. 表达式树：三种表达式的统一来源#

2.1 三种遍历对应三种表达式#

3. 中缀表达式求值：双栈法#

3.1 规则#

3.2 模拟 3 + 4 * 2 / (1 - 5)^2#

3.3 双栈法与后序遍历的关系#

4. 中缀转后缀：调度场算法#

4.1 规则#

4.2 模拟 3 + 4 * 2 / (1 - 5)^2#

5. 后缀表达式求值#

5.1 规则#

5.2 模拟 3 4 2 * 1 5 - 2 ^ / +#

6. 前缀表达式求值#

6.1 规则#

6.2 模拟 + 3 / * 4 2 ^ - 1 5 2#

7. 三种求值方法对比#

8. 递归下降求值（扩展）#

9. 总结#

10. 推荐练习#

分享文章

沿着主题读

3.2 模拟 `3 + 4 * 2 / (1 - 5)^2`#

4.2 模拟 `3 + 4 * 2 / (1 - 5)^2`#

5.2 模拟 `3 4 2 * 1 5 - 2 ^ / +`#

6.2 模拟 `+ 3 / * 4 2 ^ - 1 5 2`#