Lecture 10：栈在表达式求值中的应用

10.1 三种表达式

10.1.1 中缀表达式

定义：#中缀表达式

描述： 中缀表达式是我们平时数学运算中最常用的表达式形式，运算符写在两个操作数中间。

例子 $$ a+b $$

$$ a+b-c\times d $$

$$ ((15\div(7-(1+1)))\times3)-(2+(1+1)) $$

特点

• 符合人的书写习惯。
• 需要考虑：
  • 运算符优先级；
  • 括号；
  • 运算结合性。
• 计算机直接处理较麻烦，通常会借助栈转换或求值。

10.1.2 前缀表达式

定义：#前缀表达式

描述： 前缀表达式又称波兰表达式，运算符写在两个操作数前面。

英文名称： $$ \text{Polish notation} $$

规则

• 运算符在两个操作数前面。
• 形式为： $$ \text{运算符}\quad \text{左操作数}\quad \text{右操作数} $$

例子

原 PDF 中的紧凑写法：

+ab
-+abc
-+ab*cd

10.1.3 后缀表达式

定义：#后缀表达式

描述： 后缀表达式又称逆波兰表达式，运算符写在两个操作数后面。

英文名称： $$ \text{Reverse Polish notation} $$

规则

• 运算符在两个操作数后面。
• 形式为： $$ \text{左操作数}\quad \text{右操作数}\quad \text{运算符} $$

例子

原 PDF 中的紧凑写法：

ab+
ab+c-
ab+cd*-

解释

• 对于： $$ (a+b)-c $$
• 先把 $a+b$ 的结果作为整体：

a b +

• 再和 $c$ 相减，运算符放到后面：

a b + c -

• 对于： $$ (a+b)-(c\times d) $$
• 先得到：

a b +

• 再得到：

c d *

• 最后相减：

a b + c d * -

10.2 中缀转后缀的手算方法

10.2.1 基本步骤

题型：#中缀转后缀

第一部分：解题方法

1. 确定中缀表达式中各个运算符的运算顺序。
2. 选择下一个运算符，按照“左操作数 右操作数 运算符”的方式组合成一个新的操作数。
3. 如果还有运算符没有被处理，就继续第 2 步。

核心

• 后缀表达式中，运算符在两个操作数后面。
• 每处理一个运算符，就把它和对应的两个操作数组成一个整体。

图示信息结构化

• 括号先确定局部整体，优先级再确定乘除先于加减，结合性处理同级运算符。
• 每确定一个运算步骤，就把“左操作数、右操作数、运算符”作为一个新的整体继续参与转换。

10.2.2 左优先原则

规则

• 从左往右扫描。
• 每遇到一个可以生效的运算符，就让该运算符前面最近的两个操作数执行对应运算。
• 只要左边的运算符能计算，就优先计算左边的。

注意

• 后缀表达式的运算符生效顺序和手算转换顺序一致。
• 同优先级运算符通常按左结合处理。
• 这就是原 PDF 强调的“左优先原则”。

10.2.3 例题：复杂中缀转后缀

原 PDF 例子： $$ ((15\div(7-(1+1)))\times3)-(2+(1+1)) $$

运算顺序

最终后缀表达式

15 7 1 1 + - / 3 * 2 1 1 + + -

图示解读

• 图中圆圈编号表示中缀表达式各运算符的生效次序；后缀表达式中的运算符出现次序与之相同。
• 蓝色括线表示每个运算符对应的两个操作数整体，能直观看出嵌套子表达式如何逐层合并。
• 最终结果仍以空格分隔的后缀序列为准，避免多位数 15 与相邻数字混淆。

第二部分：典型例题

例题：将 $a+b-c\times d$ 转为后缀表达式

先算乘法： $$ c\times d $$ 对应：

c d *

再处理 $a+b$：

a b +

最后相减：

a b + c d * -

第三部分：知识点复盘

• 中缀转后缀时，同优先级按左优先。
• 括号会改变运算顺序。
• 后缀表达式不需要括号也能明确运算顺序。

10.3 中缀转前缀的手算方法

10.3.1 基本步骤

题型：#中缀转前缀

第一部分：解题方法

1. 确定中缀表达式中各个运算符的运算顺序。
2. 选择下一个运算符，按照“运算符 左操作数 右操作数”的方式组合成一个新的操作数。
3. 如果还有运算符没有被处理，就继续第 2 步。

注意

• 中缀转前缀手算时，原 PDF 采用右优先原则。
• 也就是遇到同优先级、同层次运算符时，优先处理右边可计算的部分。
• “右优先”只是构造前缀表达式时保持原结合关系的手算策略；不能交换左右操作数，也不能改变原中缀表达式的语义。

10.3.2 例题：中缀转前缀

原 PDF 例子： $$ 6+3\times(7-4)-8\div2 $$

运算顺序

最终前缀表达式

- + 6 * 3 - 7 4 / 8 2

原 PDF 紧凑写法：

-+6*3-74/82

上表已经完整保留原图的运算顺序和前缀结果；原图中的两个空栈只是手算辅助框，不包含额外算法信息，因此不再重复嵌入。

第二部分：典型例题

例题：将 $(a+b)-(c\times d)$ 转为前缀表达式

先得到：

+ a b

再得到：

* c d

最后整体相减：

- + a b * c d

第三部分：知识点复盘

• 前缀表达式中运算符在操作数前面。
• 中缀转前缀时，组合方式是： $$ \text{运算符}\quad \text{左操作数}\quad \text{右操作数} $$
• 手算时注意右优先原则。

10.4 后缀表达式算法

10.4.1 用栈实现后缀表达式计算

定义：#后缀表达式求值

描述： 后缀表达式求值是从左往右扫描表达式，遇到操作数入栈，遇到运算符就弹出两个操作数进行运算，再把结果压回栈。

算法步骤

1. 从左往右扫描下一个元素，直到处理完所有元素。
2. 若扫描到操作数，则压入栈，并回到第 1 步。
3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算。
4. 将运算结果压回栈顶，再回到第 1 步。

重要注意

• 先出栈的是右操作数。
• 后出栈的是左操作数。
• 对于减法和除法，这一点非常重要。

若先出栈的是 $b$，后出栈的是 $a$，遇到运算符 -，应计算： $$ a-b $$

遇到运算符 /，应计算： $$ a\div b $$

合法表达式的结果

• 如果后缀表达式合法，最后栈中只会留下一个元素。
• 这个元素就是最终结果。

10.4.2 后缀求值例题

以后缀表达式为例：

15 7 1 1 + - / 3 * 2 1 1 + + -

它来自中缀表达式： $$ ((15\div(7-(1+1)))\times3)-(2+(1+1)) $$

计算过程

最终结果： $$ 5 $$

10.5 中缀表达式算法

10.5.1 用栈实现中缀表达式计算

定义：#中缀表达式求值

描述： 中缀表达式求值可以用两个栈实现，一个保存操作数，一个保存运算符。

需要两个栈

• 操作数栈。
• 运算符栈。

基本规则

1. 若扫描到操作数，压入操作数栈。
2. 若扫描到运算符或界限符，则按照“中缀转后缀”的逻辑处理运算符栈。
3. 处理过程中，每当弹出一个运算符，就再弹出两个操作数栈的栈顶元素并执行相应运算。
4. 运算结果再压回操作数栈。

一句话理解

• 中缀表达式的计算可以看成：
  • 先把中缀转后缀；
  • 再对后缀表达式求值；
  • 也可以在转换过程中同步完成计算。

10.6 中缀表达式转后缀表达式：栈算法

10.6.1 方法

初始化

• 初始化一个栈。
• 该栈用于保存暂时还不能确定运算顺序的运算符。

扫描方向

• 从左到右处理各个元素，直到末尾。

10.6.2 可能遇到的三种情况

情况一：遇到操作数

• 直接加入后缀表达式。

例子

a

直接输出：

a

情况二：遇到界限符

遇到左括号 (

• 直接入栈。

遇到右括号 )

• 依次弹出栈内运算符，并加入后缀表达式。
• 直到弹出 ( 为止。
• 注意：( 不加入后缀表达式。

情况三：遇到运算符

• 对本节的 +、-、*、/ 左结合二元运算符，依次弹出栈中优先级高于或等于当前运算符的所有运算符。
• 弹出的运算符加入后缀表达式。
• 如果遇到 ( 或栈空，则停止弹出。
• 最后把当前运算符入栈。

处理完所有字符后

• 将栈中剩余运算符依次弹出。
• 弹出的运算符依次加入后缀表达式。

结合性补充

• 通用规则是：栈顶优先级更高时弹出；优先级相等时，仅当当前运算符为左结合时弹出。
• 若扩展到右结合的幂运算符（如 ^），遇到同级 ^ 时不能按本节规则直接弹出。
• 一元运算符还需要单独定义优先级、结合性和操作数个数，不能直接套用二元运算符规则。

10.6.3 运算符优先级

同级处理

• 本节四种运算符均按左结合。
• 因此遇到当前运算符时，栈顶同级运算符也要先弹出。
• “高于或等于当前运算符都弹出”只适用于这里的左结合二元运算符集合。

10.6.4 伪代码

初始化运算符栈 opStack
初始化后缀表达式 postfix

从左到右扫描中缀表达式：
    如果是操作数：
        加入 postfix

    如果是 '('：
        入 opStack

    如果是 ')'：
        不断弹出 opStack 栈顶运算符并加入 postfix
        直到弹出 '('

    如果是运算符 op：
        当 opStack 非空，且栈顶不是 '('，
        且（栈顶优先级更高，
            或二者同级且当前 op 为左结合）：
            弹出栈顶运算符并加入 postfix
        将 op 入 opStack

扫描结束后：
    将 opStack 中剩余运算符依次弹出并加入 postfix

10.7 三种算法汇总

10.7.1 用栈实现中缀转后缀

• 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
• 从左到右处理各个元素，直到末尾。
• 遇到操作数，直接加入后缀表达式。
• 遇到 (，直接入栈。
• 遇到 )，依次弹出栈内运算符并加入后缀表达式，直到弹出 (。
• 遇到本节的左结合二元运算符，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式。
• 遇到 ( 或栈空则停止弹出，再把当前运算符入栈。
• 所有字符处理完后，将栈中剩余运算符依次弹出并加入后缀表达式。

10.7.2 用栈实现后缀表达式计算

• 从左往右扫描下一个元素，直到处理完所有元素。
• 若扫描到操作数，则压入栈。
• 若扫描到运算符，则弹出两个栈顶元素，执行相应运算。
• 运算结果压回栈顶。
• 先出栈的是右操作数。
• 合法表达式最后栈中只剩一个元素，即最终结果。

10.7.3 用栈实现中缀表达式计算

• 初始化两个栈：
  • 操作数栈；
  • 运算符栈。
• 若扫描到操作数，压入操作数栈。
• 若扫描到运算符或界限符，则按照“中缀转后缀”的逻辑处理运算符栈。
• 每弹出一个运算符，就弹出两个操作数并执行相应运算。
• 结果压回操作数栈。

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：栈在括号匹配中的应用 · 下一篇：栈在递归中的应用
• 关联专题：栈与队列代码

10.8 本节复盘

必须掌握

• 前缀表达式：运算符在操作数前面。
• 后缀表达式：运算符在操作数后面。
• 中缀表达式：运算符在两个操作数中间。
• 中缀转后缀手算使用左优先原则。
• 中缀转前缀手算使用右优先原则。
• 后缀表达式求值从左往右扫描。
• 后缀求值遇到操作数入栈，遇到运算符弹出两个操作数计算。
• 后缀求值中，先出栈的是右操作数。
• 中缀表达式求值可用两个栈：
  • 操作数栈；
  • 运算符栈。

易错点

• 后缀表达式中，a b - 表示 $a-b$，不是 $b-a$。
• 后缀求值时先出栈的是右操作数。
• 中缀转后缀时，遇到 ) 要弹出到 ( 为止，但 ( 不加入后缀表达式。
• 中缀转后缀时，遇到同级运算符是否弹栈取决于当前运算符的结合性：左结合弹出，右结合不先弹出。
• 前缀、后缀表达式本身不需要括号。

一句话总结

• 表达式求值的核心是把“运算顺序”显式化；后缀表达式用栈最容易计算，中缀表达式可以先转后缀，也可以用两个栈边转边算。