逆波蘭表示法

逆波蘭表示法（Reverse Polish notation，RPN，或逆波蘭記法），是一種是由波蘭數學家揚·武卡謝維奇1920年引入的數學表達式方式，在逆波蘭記法中，所有操作符置於操作數的後面，因此也被稱為後綴表示法。逆波蘭記法不需要括號來標識操作符的優先級。

逆波蘭結構由弗里德里希·鮑爾（Friedrich L. Bauer）和艾茲格·迪科斯徹在1960年代早期提議用於表達式求值，以利用堆棧結構和減少計算機內存訪問。逆波蘭記法和相應的算法由澳大利亞哲學家、計算機學家查爾斯·漢布林（Charles Hamblin）在1960年代中期擴充[1][2]

在1960和1970年代，逆波蘭記法廣泛地被用於台式計算器，因此也在普通公眾（工程、商業和金融領域）中使用。

逆波蘭記法中，操作符置於操作數的後面。例如表達“三加四”時，寫作“3 4 +”，而不是“3 + 4”。如果有多個操作符，操作符置於第二個操作數的後面，所以常規中綴記法的“3 - 4 + 5”在逆波蘭記法中寫作“3 4 - 5 +”：先3減去4，再加上5。使用逆波蘭記法的一個好處是不需要使用括號。例如中綴記法中“3 - 4 * 5”與“（3 - 4）*5”不相同，但後綴記法中前者寫做“3 4 5 * -”，無歧義地表示“3 (4 5 *) −”；後者寫做“3 4 - 5 *”。

逆波蘭表達式的解釋器一般是基於堆棧的。解釋過程一般是：操作數入棧；遇到操作符時，操作數出棧，求值，將結果入棧；當一遍後，棧頂就是表達式的值。因此逆波蘭表達式的求值使用堆棧結構很容易實現，和能很快求值。

注意：逆波蘭記法並不是簡單的波蘭表達式的反轉。因為對於不滿足交換律的操作符，它的操作數寫法仍然是常規順序，如，波蘭表示法“/ 6 3”的逆波蘭表示法是“6 3 /”而不是“3 6 /”；數字的數位寫法也是常規順序。

艾茲格·迪科斯徹引入了shunting yard算法，用於將中綴表達式轉換為後綴形式。因其操作類似於火車編組場而得名。 大多數操作符優先級解析器能轉換為處理後綴表達式，實際中，一般構造抽象語法樹，樹的後序遍歷即為逆波蘭記法。

偽代碼

while有輸入符號

讀入下一個符號

IF是一個操作數

入棧

ELSE IF是一個操作符

有一個先驗的表格給出該操作符需要n個參數

IF堆棧中少於n個操作數

（錯誤） 用户沒有輸入足夠的操作數

Else，n個操作數出棧

計算操作符。

將計算所得的值入棧

IF棧內只有一個值

這個值就是整個計算式的結果

ELSE多於一個值

（錯誤） 用户輸入了多餘的操作數

第一代實現了逆波蘭架構的電子計算機是英國電氣公司1963年交付使用的KDF9和美國的Burroughs B5000。Friden公司在它1963年推出的EC-130中，將逆波蘭表達式引入了台式計算器市場。惠普1968年設計了9100A逆波蘭計算器，首台手持式計算器HP-35也使用逆波蘭表達式，惠普在HP-10A之前的所有手持計算器（包括科學計算，金融和可編程）中使用了逆波蘭表達式，並在1980年代晚期的LCD顯示計算器如HP-10C, HP-11C, HP-15C, HP-16C，等都是用了逆波蘭表達式。

當有操作符時就計算，因此，表達式並不是從右至左整體計算而是每次由中心向外計算一部分，這樣在複雜運算中就很少導致操作符錯誤。

堆棧自動記錄中間結果，這就是為什麼逆波蘭計算器能容易對任意複雜的表達式求值。與普通科學計算器不同，它對錶達式的複雜性沒有限制。

逆波蘭表達式中不需要括號，用户只需按照表達式順序求值，讓堆棧自動記錄中間結果；同樣的，也不需要指定操作符的優先級。

逆波蘭計算器中，沒有“等號”鍵用於開始計算。

逆波蘭計算器需要“確認”鍵用於區分兩個相鄰的操作數。

機器狀態永遠是一個堆棧狀態，堆棧裏是需要運算的操作數，棧內不會有操作符。

教育意義上，逆波蘭計算器的使用者必須懂得要計算的表達式的含義。

目前逆波蘭的實現有：

任何基於棧的程序語言：

Forth

Factor語言

PostScript語言。

Windows下逆波蘭計算器

Windows XP下的Microsoft PowerToy calculator

手機逆波蘭計算器開源的JAVA計算器

Palm PDA下的逆波蘭計算器

Mac OS X計算器

Mac OS X和iPhone下的逆波蘭計算器

Unix下的計算程序dc

交互式JavaScript的逆波蘭計算器：

rpn-calculator

Wikibooks:Ada Programming/Mathematical calculations (Ada語言中的逆波蘭計算器)

Emacs的lisp lib包: calc

基於GTK+的galculator

表達式轉換