基本介紹
- 中文名：逆波蘭表示法
- 外文名：Reverse Polish notation
- 別名：逆波蘭記法
- 發明者：揚·武卡謝維奇
簡介,解釋,與中綴記法的轉換,逆波蘭表達式求值,實現,實際意義,
簡介
逆波蘭表示法（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
表達式轉換
