逆波蘭表示法

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