逆波蘭表示法

逆波蘭表示法（也稱為字尾表示法，簡稱 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