中缀、后缀表达式与栈

01 | 引言

我们熟悉的算式，通常把运算符写在两个操作数之间，这种形式称为中缀表达式。

例如

a + b \times (c - d) - e \div f

它的计算顺序由运算符优先级、结合性和括号共同决定。

20 世纪初，波兰逻辑学家 Jan Łukasiewicz 提出了波兰表示法，将运算符写在操作数之前，即前缀表达式。与之对应的，把运算符写在操作数之后的形式称为后缀表达式，也叫逆波兰表示法（Reverse Polish Notation，RPN）。

同一个表达式可以写成：

表达形式	表达式
中缀	`a + b * (c - d) - e / f`
前缀	`- + a * b - c d / e f`
后缀	`a b c d - * + e f / -`

这三种形式表达的运算相同。中缀表达式符合日常书写习惯；后缀表达式则通过操作数和运算符的排列确定计算顺序，因此不需要括号，求值时也不需要比较运算符优先级。

02 | 中缀表达式的计算

1. 与栈的关联

从左向右扫描中缀表达式时，并不是遇到一个运算符就能立即计算。

例如，读到乘号后，如果右边是一个括号表达式，就必须先算出括号内的结果。因此，需要暂存已经读到的操作数，以及尚不能执行的运算符。

我们设置两个栈：

栈	名称	保存的内容
操作数栈	`opnd`	操作数和中间结果
运算符栈	`optr`	等待处理的运算符、左括号和栈底界符

按照约定，初始化时，先把 = 压入运算符栈；输入表达式的末尾也保留一个 =。

以 12*(6-3.5)= 为例，初始状态为：

待扫描输入：12 * ( 6 - 3.5 ) =

操作数栈 opnd：空
运算符栈 optr：[=]

这里的两个 = 分别承担不同的控制作用：

栈底的 =：作为运算符栈的边界，在扫描前压入。
输入末尾的 =：表示输入结束，触发剩余运算，最终与栈底的 = 匹配。

它们都不参与算术运算，也不表示赋值。

2. 运算符的优先关系

为了判断是执行当前运算符入栈还是执行栈顶运算符，分别定义：

ISP（In-Stack Priority）：运算符在栈内时的优先级。
ICP（Incoming Priority）：当前读入运算符的栈外优先级。

采用如下优先级表：

运算符	`=`	`(`	`*`、`/`	`+`、`-`	`)`
栈内优先级 ISP	0	1	5	3	6
栈外优先级 ICP	0	6	4	2	1

不难发现，右括号只用于触发计算和括号匹配，实际上不会入栈，因此不会用到它的栈内优先级。

设当前读入的运算符为 $θ_{1}$ ，栈顶运算符为 $θ_{2}$ ，比较：

I C P (θ_{1}) 与 I S P (θ_{2})

处理规则如下：

比较结果	处理方式	是否读取下一个元素
$I C P (θ_{1}) > I S P (θ_{2})$	当前运算符入栈	是
$I C P (θ_{1}) < I S P (θ_{2})$	弹出栈顶运算符，取两个操作数计算，再将结果压栈	否，继续用当前运算符比较
$I C P (θ_{1}) = I S P (θ_{2})$	匹配并消去一对括号，或匹配两个 `=` 后结束	括号匹配后继续读取；界符匹配后结束

这套优先级有三个值得理解的设计：

第一，普通运算符的栈内优先级高于同级运算符的栈外优先级。

例如，已有减号在栈内，又读到一个减号时：

I C P (-) = 2 < I S P (-) = 3

因此先执行栈内的减法，保证同级运算按照从左到右的顺序进行。

第二，左括号在栈外时优先级高，入栈后优先级低。

这样，左括号能够顺利入栈，而括号内部的运算符也能继续压在它上面。读到右括号时，先处理括号内的运算；当栈顶变成左括号时：

I C P ()) = 1 = I S P (()

此时弹出左括号，跳过右括号，不进行算术运算。

第三，输入末尾的 = 优先级最低。

它会促使栈内尚未执行的算术运算依次完成，直到：

I C P (=) = 0 = I S P (=)

两个界符匹配，算法结束。

3. 双栈求值的完整流程

从左向右扫描表达式：

遇到操作数：识别完整的数，压入 opnd，继续读取。
遇到运算符、括号或结束界符：按照 ICP / ISP 规则处理。
需要计算时：从 optr 弹出运算符，再从 opnd 依次弹出右操作数 b 和左操作数 a，计算 a θ b，将结果压回 opnd。
两个 = 匹配时：弹出栈底界符，结束处理。对于合法表达式，opnd 中应恰好剩下一个结果。

其中，最容易遗漏的是：

弹出栈顶运算符并完成一次计算后，当前读入的元素尚未处理完，必须继续与新的栈顶比较。

4. 例：`12*(6-3.5)=`

步骤	当前元素	主要操作	`opnd`	`optr`
初始	—	将栈底界符 `=` 入栈	空	`=`
1	`12`	将完整的数 `12` 入栈	`12`	`=`
2	`*`	$4 > 0$ ，乘号入栈	`12`	`= *`
3	`(`	$6 > 5$ ，左括号入栈	`12`	`= * (`
4	`6`	操作数入栈	`12 6`	`= * (`
5	`-`	$2 > 1$ ，减号入栈	`12 6`	`= * ( -`
6	`3.5`	将完整的数 `3.5` 入栈	`12 6 3.5`	`= * ( -`
7	`)`	$1 < 3$ ，弹出减号，计算 `6-3.5`；保留当前 `)`	`12 2.5`	`= * (`
8	`)`	$1 = 1$ ，弹出左括号，跳过右括号	`12 2.5`	`= *`
9	`=`	$0 < 5$ ，弹出乘号，计算 `12*2.5`；保留当前 `=`	`30`	`=`
10	`=`	$0 = 0$ ，弹出栈底界符，结束	`30`	空

其中，右括号的处理分为两步。

先计算括号内的减法：

6 - 3.5 = 2.5

此时右括号仍未处理完，要继续与新的栈顶左括号比较，完成括号匹配。

同样，读到末尾的 = 后，先计算：

12 \times 2.5 = 30

然后继续用这个 = 与栈底界符比较，匹配后结束。

最终，操作数栈中唯一的元素就是表达式的值：

30

03 | 后缀表达式的计算

1. 一个操作数栈即可完成求值

后缀表达式中，运算符位于它所作用的两个操作数之后。扫描到运算符时，它所需的两个操作数或子表达式结果已经在栈中。

因此，求值时只需要一个操作数栈 opnd：

遇到操作数：压栈。
遇到二元运算符：先弹出右操作数 b，再弹出左操作数 a，计算 a θ b，将结果压栈。
扫描结束：对于合法表达式，栈中应恰好剩下一个元素，即最终结果。

这里不需要运算符栈，也不需要用 = 比较优先级；扫描到后缀序列末尾即可结束。

2. 例：`12 6 2 / 0.5 - *`

步骤	当前元素	主要操作	`opnd`：栈底 → 栈顶
1	`12`	操作数入栈	`12`
2	`6`	操作数入栈	`12 6`
3	`2`	操作数入栈	`12 6 2`
4	`/`	先弹出 `2`，再弹出 `6`，将 `6/2=3` 压栈	`12 3`
5	`0.5`	操作数入栈	`12 3 0.5`
6	`-`	先弹出 `0.5`，再弹出 `3`，将 `3-0.5=2.5` 压栈	`12 2.5`
7	`*`	先弹出 `2.5`，再弹出 `12`，将 `12*2.5=30` 压栈	`30`

最终结果为：

30

3. 操作数的弹出顺序

以本例中的除法为例，读到 / 时，栈的状态是：

┌─────┐
│  2  │  ← 栈顶，先弹出：右操作数 b
├─────┤
│  6  │  ← 后弹出：左操作数 a
├─────┤
│ 12  │
└─────┘

计算的是：

a \div b = 6 \div 2

无论中缀求值还是后缀求值，都应遵守同一规则：先弹出右操作数，后弹出左操作数，按照“左操作数运算符右操作数”的顺序计算。

now you can try leetcode LCR 036. 逆波兰表达式求值

04 | 中缀表达式转为后缀表达式

1. 从“执行运算”改为“输出运算符”

理解了双栈求值，中缀转后缀就容易了。

在双栈求值中，运算符出栈意味着“现在可以执行这一步计算”；在中缀转后缀中，运算符出栈意味着“现在可以把它写入后缀表达式”。

因此，可以继续使用同一套 ICP / ISP 规则，只需调整两点：

遇到操作数时，直接输出。
算术运算符出栈时，输出该运算符。

转换过程只需要一个运算符栈 optr，以及一个保存输出结果的序列。

初始化时，同样先将 = 压入运算符栈，并在待扫描的中缀表达式末尾添加 =。

2. 转换规则

当前元素或情况	处理方式
操作数	直接输出，继续读取
当前算术运算符的 ICP 大于栈顶的 ISP	当前运算符入栈，继续读取
当前算术运算符的 ICP 小于栈顶的 ISP	弹出并输出栈顶算术运算符，继续用当前运算符比较
左括号 `(`	入栈，继续读取
右括号 `)`	依次弹出并输出括号内的算术运算符；遇到左括号后将其弹出，跳过右括号
结束界符 `=`	依次弹出并输出剩余算术运算符；遇到栈底 `=` 后将其弹出，结束

3. 例：`a+b*(c-d)-e/f`

下表每行展示当前元素处理完毕后的状态；其中，一次处理可能包含多次弹栈。

当前元素	主要操作	`optr`：栈底 → 栈顶	已输出的后缀序列
初始	将界符 `=` 入栈	`=`	空
`a`	直接输出	`=`	`a`
`+`	入栈	`= +`	`a`
`b`	直接输出	`= +`	`a b`
`*`	$4 > 3$ ，入栈	`= + *`	`a b`
`(`	入栈	`= + * (`	`a b`
`c`	直接输出	`= + * (`	`a b c`
`-`	$2 > 1$ ，入栈	`= + * ( -`	`a b c`
`d`	直接输出	`= + * ( -`	`a b c d`
`)`	弹出并输出 `-`，再消去一对括号	`= + *`	`a b c d -`
`-`	依次弹出并输出 `*`、`+`，再将当前 `-` 入栈	`= -`	`a b c d - * +`
`e`	直接输出	`= -`	`a b c d - * + e`
`/`	$4 > 3$ ，入栈	`= - /`	`a b c d - * + e`
`f`	直接输出	`= - /`	`a b c d - * + e f`
`=`	依次弹出并输出 `/`、`-`，最后匹配并弹出栈底 `=`	空	`a b c d - * + e f / -`

这里重点看括号之后的减号。

当前读入 - 时，栈中为：

[=, +, *]

首先：

I C P (-) = 2 < I S P (*) = 5

所以弹出并输出 *。

当前减号仍未处理完，继续比较：

I C P (-) = 2 < I S P (+) = 3

再弹出并输出 +。

最后，栈顶只剩界符：

I C P (-) = 2 > I S P (=) = 0

这时才将当前减号入栈，并读取下一个元素。

最终得到后缀表达式：

a b c d - * + e f / -

其中，c d - 先形成括号内的结果，再与 b 相乘、与 a 相加，最后减去 e f / 的结果。

后缀表达式不需要括号，因为括号原本指定的运算顺序，已经体现在操作数和运算符的排列中。

05 | 总结

表达式处理中，栈的作用是暂存已经遇到、后续仍需使用的内容：

中缀求值：用两个栈分别保存操作数、中间结果和等待执行的运算符。
后缀求值：用一个操作数栈，遇到运算符就取出操作数计算。
中缀转后缀：用一个运算符栈，按照优先关系确定运算符的输出顺序。

掌握流程时，尤其要记住三个细节：

使用界符法时，必须先将 = 压入运算符栈，并用输入末尾的 = 完成收尾。
弹出一个算术运算符后，当前输入元素不前移，要继续与新的栈顶比较。
取两个操作数时，先弹出右操作数，再弹出左操作数。