后缀表达式

后缀表示法（Postfix notation），又称逆波兰表示法，
其所有操作符置于操作数的后面，使用后缀表示法表示的表达式称为后缀表达式.
使用后缀表示法，能较大地简化计算机表达式求值.

我们通常使用的带括号的表达式即为中缀表达式（Infix expression），例如 $1+(2\times3)$，其对应的后缀表达式是 $1\ 2\ 3\ \times\ +$.

本文主要介绍后缀表达式的计算机求值和将中缀表达式转化为后缀表达式.

当然，还存在前缀表达式（Prefix expression），例如上面的例子（$1+(2\times3)$），其对应的前缀表达式为 $+\ 1\ \times\ 2\ 3$.

细心的读者可能已经注意到了，前缀表达式和后缀表达式都有一个优点：不需要括号，而且它们都可以通过栈（Stack）十分方便地进行运算.

前缀表达式不是本文的重点，故不再赘述.

warning

以下内容默认运算符都是二元运算符（例如$+,-,\times,\div$）

---

后缀表达式求值

考虑一条后缀表达式：

$$3\ 1\ 2\ -\ \times$$

它对应的中缀表达式是 $3\times(1-2)=-3$.

---

后缀表达式求值的操作如下:

我们建立一个存储数字的栈 S，然后从左向右依次扫描后缀表达式，对每个元素 n，我们讨论其类型：

• 若 n 为数字，将其入栈；
• 若 n 为运算符（不妨记为 op），依次取出栈顶的数字 b, a，运算 a op b，并将运算结果入栈. 若栈内不足两个数字，说明表达式错误.

若表达式正确，最终栈内应只含一个数字，它就是后缀表达式的运算结果.

---

例如，对于后缀表达式$3\ 1\ 2\ -\ \times$，我们如下操作：

• 第一位 $3$ 是数字，将其入栈. 此时 $S=\{3\}$；
• 第二位 $1$ 是数字，将其入栈. 此时 $S=\{3,1\}$；
• 第三位 $2$ 是数字，将其入栈. 此时 $S=\{3,1,2\}$；
• 第四位 $-$ 是运算符，取出栈顶元素 $1$ 和 $2$，计算 $1-2=-1$，将 $-1$ 入栈，此时 $S=\{3,-1\}$；
• 第五位 $\times$ 是运算符，取出栈顶元素 $3$ 和 $-1$，计算 $3\times(-1)=-3$，将 $-3$ 入栈，此时 $S=\{-3\}$.

扫描结束，最终运算结果为 $-3$.

---

由此可见，对计算机而言，使用后缀表示法计算是十分方便的.

---

中缀表达式转后缀表达式

还是以 $3\times(1-2)$ 即 $3\ 1\ 2\ -\ \times$ 为例.

---

转换算法如下：

建立一个存储运算符的栈 S，然后从左向右依次扫描中缀表达式，对每个元素 n，我们讨论其类型：

• 若 n 为数字，直接输出；
• 若 n 为左括号，入栈 “(” 字符；
• 若 n 为右括号，不断取出栈顶并输出，直到 “(” 字符，然后取出 “(” 字符；
• 若 n 为运算符，如果栈顶存在且优先级不低于新符号，就不断取出栈顶并输出. 然后将新符号入栈.

扫描结束，依次取出栈顶元素并输出.

参见优先级表.

---

例如，对于 $3\times(1-2)$，我们有如下操作（记转换后的后缀表达式为 P）：

• 第一位 $3$ 是数字，直接输出. $P=\{3\}$，$S=\varnothing$；
• 第二位 $\times$ 是运算符，不存在栈顶，直接入栈. $P=\{3\}$，$S=\{\times\}$；
• 第三位 $($ 是左括号，直接入栈. $P=\{3\}$，$S=\{\times,(\}$；
• 第四位 $1$ 是数字，直接输出. $P=\{3,1\}$，$S=\{\times,(\}$；
• 第五位 $-$ 是运算符，栈顶符号 $($ 优先级低于 $-$，不输出，直接入栈. $P=\{3\}$，$S=\{\times,(,-\}$；
• 第六位 $2$ 是数字，直接输出. $P=\{3,1,2\}$，$S=\{\times,(,-\}$；
• 第七位 $)$ 是右括号，不断取出栈顶并输出. $P=\{3,1,2,-\}$，$S=\{\times\}$.

扫描结束，不断取出栈顶并输出，$P=\{3,1,2,-,\times\}$.

这样我们就得到了需要的后缀表达式 $3\ 1\ 2\ -\ \times$.

---

若感兴趣，可以尝试使用 C++ 写一下中缀表达式的计算方法.