逆波兰表示法

逆波兰表示法（也称为后缀表示法，简称 RPN）是一种表示数学表达式的方

运算符没有内在原因必须写在操作数之间，就像标准算术运算符那样。运算符可

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

我们习惯于看到中缀形式的算术和前缀形式的函数，通常使用括号（例如

>>> 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

扩展：基于堆栈的编程语言 一些编程语言称为基于堆栈的编程语言，在整个过程中使用基于堆栈的

逆波兰表达式的求值

用逆波兰表示法表示的表达式可以使用堆栈轻松求值。当读取表达式时，值将被推入堆栈。当读到运算符时，值将从堆栈中弹出，结果将被推回堆栈。留在堆栈上的结果是表达式的总值。

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

堆栈如何用于计算逆波兰表示法的示例。

示例

使用比上面更复杂的示例，"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