逆波兰表示法

逆波兰表示法（也称为后缀表示法，简称 RPN）是一种表示数学表达式的形式。这种表示法之所以被使用是因为表达式所处的格式对于机器来说更容易理解，而不是我们习惯的表示法（中缀表示法），在中缀表示法中，运算符位于数字之间。表达式可以是复杂的，也可以是简单的。RPN 不需要括号，因为表达式的排列方式使得机器不需要括号就能理解。

没有内在的理由说明运算符必须写在线算符之间，就像标准算术运算符一样。运算符可以出现在运算符之前（前缀）、之间（中缀）或之后（后缀）。以下是用三种格式写的同一个表达式

前缀表示法	中缀表示法	后缀表示法
× 3 4	3 × 4	3 4 ×

我们习惯于看到算术运算以中缀形式写出，而函数则以前缀形式写出，通常使用括号（例如 sqrt(9) 表示开平方根操作）。我们可以用相同的形式写算术运算，例如使用 Python 的 operator 库

>>> import operator
>>> operator.add(operator.mul(3, 4), 2)
14

后缀表示法的优点

前缀表示法和后缀表示法都不需要括号来表达操作分组：求值顺序完全由操作顺序决定。

中缀表示法只能轻松地表达接受一个或两个参数的操作（例如二元加法或开平方根）。接受两个以上参数的操作需要排版上的修饰，例如括号。

等效方程

后缀	中缀	答案
3 4 +	3 + 4	7
5 6 + 3 *	(5 + 6) * 3	33
2 4 / 5 6 - *	(2/4)*(5-6)	-0.5
2 3 ↑	2³	8

扩展：基于堆栈的编程语言 一些编程语言，称为基于堆栈的编程语言，在整个过程中都使用基于堆栈的求值模型。最著名的基于堆栈的语言是 PostScript 和 Forth。

逆波兰表达式的求值

以逆波兰表示法表示的表达式可以用一个 堆栈 很容易地求值。当读取表达式时，值被压入堆栈中。当读取操作时，值被弹出堆栈，结果被压回堆栈。留在堆栈中的结果是表达式的总体值。

使用堆栈和统一的优先级规则使得编写代码来计算逆波兰表达式的结果变得非常容易。

一个关于如何使用堆栈来计算逆波兰表示法的例子。

例子

使用一个比上面稍微复杂一点的例子，"3 4 × 10 2 ÷ +" 的求值可以按如下进行

未读输入	堆栈	注释
3 4 × 10 2 ÷ +	_	堆栈在求值开始时为空
4 × 10 2 ÷ +	3	值 3 被压入
× 10 2 ÷ +	4 3	值 4 被压入
10 2 ÷ +	12	× 运算符从堆栈中弹出两个项，将它们相乘，并将结果压回堆栈
2 ÷ +	10 12	值 10 被压入
÷ +	2 10 12	值 2 被压入
+	5 12	÷ 运算符从堆栈中弹出两个项，将其中一个除以另一个，并将结果压回堆栈
	17	+ 运算符从堆栈中弹出两个项，将它们相加，并将结果压回堆栈

留在堆栈中的结果 17 是表达式的总体值。

练习题

练习：中缀到 RPN 的转换 将 x + y 转换为 RPN。 答案 x y + 将 (x + y)*z 转换为 RPN。 答案 x y + z * 将 3 / (5 + y * x) 转换为 RPN。 答案 3 5 y x * + /

练习：RPN 到中缀的转换 将 x y * 转换为中缀。 答案 x * y 将 5 y + z x 3 - * / 转换为中缀。 答案 (5 + y) / (z * (x - 3))

YouTube 视频示例

可以在 Youtube 上的 Computerphile 频道看到一个视频示例：https://www.youtube.com/watch?v=7ha78yWRDlE