逆波蘭表示法
|
| 前綴表示法 （+ 3 4 ） |
| 中綴表示法 （3 + 4） |
| 後綴表示法 （3 4 + ） |
逆波蘭表示法（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 /」；數字的數位寫法也是常規順序。
與中綴記法的轉換
艾茲格·迪科斯徹引入了調度場算法，用於將中綴表達式轉換為後綴形式。因其操作類似於火車編組場而得名。 大多數操作符優先級解析器(解析器用簡單的查表操作即可實現，優先級表由開發者自己定製，在不同的應用場景中，開發者可自由改變操作符的優先級)能轉換為處理後綴表達式，實際中，一般構造抽象語法樹，樹的後序遍歷即為逆波蘭記法。
逆波蘭表達式求值
偽代碼
- while有輸入符號
- 讀入下一個符號
- IF是一個操作數
- 入棧
- ELSE IF是一個操作符
- 有一個先驗的表格給出該操作符需要n個參數
- IF堆疊中少於n個操作數
- （錯誤） 用戶沒有輸入足夠的操作數
- Else，n個操作數出棧
- 計算操作符。
- 將計算所得的值入棧
- IF棧內只有一個值
- 這個值就是整個計算式的結果
- ELSE多於一個值
- （錯誤） 用戶輸入了多餘的操作數
例子
中綴表達式「5 + ((1 + 2) * 4) − 3」寫作
- 5 1 2 + 4 * + 3 −
下表給出了該逆波蘭表達式從左至右求值的過程，堆疊欄給出了中間值，用於跟蹤算法。
| 輸入 | 操作 | 堆疊 | 註釋 |
|---|---|---|---|
| 5 | 入棧 | 5 | |
| 1 | 入棧 | 5, 1 | |
| 2 | 入棧 | 5, 1, 2 | |
| + | 加法運算 | 5, 3 | (1, 2)出棧；將結果（3）入棧 |
| 4 | 入棧 | 5, 3, 4 | |
| * | 乘法運算 | 5, 12 | (3, 4)出棧；將結果（12）入棧 |
| + | 加法運算 | 17 | (5, 12)出棧；將結果 (17)入棧 |
| 3 | 入棧 | 17, 3 | |
| − | 減法運算 | 14 | (17, 3)出棧；將結果（14）入棧 |
計算完成時，棧內只有一個操作數，這就是表達式的結果：14
上述運算可以重寫為如下運算鏈方法（用於HP的逆波蘭計算器）：[3]
- 1 2 + 4 * 5 + 3 −
實現
第一代實現了逆波蘭架構的電子計算機是英國電氣公司1963年交付使用的KDF9和美國的Burroughs B5000。Friden公司在它1963年推出的EC-130中，將逆波蘭表達式引入了台式計算器市場。惠普1968年設計了9100A逆波蘭計算器，首台手持式計算器HP-35也使用逆波蘭表達式，惠普在HP-10A之前的所有手持計算器（包括科學計算，金融和可程式）中使用了逆波蘭表達式，並在1980年代晚期的LCD顯示計算器如HP-10C, HP-11C, HP-15C, HP-16C，等都是用了逆波蘭表達式。
實際意義
- 當有操作符時就計算，因此，表達式並不是從右至左整體計算而是每次由中心向外計算一部分，這樣在複雜運算中就很少導致操作符錯誤。
- 堆疊自動記錄中間結果，這就是為什麼逆波蘭計算器能容易對任意複雜的表達式求值。與普通科學計算器不同，它對表達式的複雜性沒有限制。
- 逆波蘭表達式中不需要括號，用戶只需按照表達式順序求值，讓堆疊自動記錄中間結果；同樣的，也不需要指定操作符的優先級。
- 逆波蘭計算器中，沒有「等號」鍵用於開始計算。
- 逆波蘭計算器需要「確認」鍵用於區分兩個相鄰的操作數。
- 機器狀態永遠是一個堆疊狀態，堆疊里是需要運算的操作數，棧內不會有操作符。
- 教育意義上，逆波蘭計算器的使用者必須懂得要計算的表達式的含義。
目前逆波蘭的實現有：
- 任何基於棧的程序語言：
- 線上的逆波蘭計算器
- Windows下逆波蘭計算器
- Windows XP下的Microsoft PowerToy calculator
- 手機逆波蘭計算器開源的JAVA計算器
- Palm PDA下的逆波蘭計算器
- Mac OS X計算器
- Mac OS X和iPhone下的逆波蘭計算器
- Unix下的計算程序dc
- 交互式JavaScript的逆波蘭計算器：[2]和[3]
- Wikibooks:Ada Programming/Mathematical calculations (Ada語言中的逆波蘭計算器)
- Emacs的lisp lib包: calc
- 基於GTK+的galculator
- 表達式轉換[4]
註釋
- ^ "Charles L. Hamblin and his work" by Peter McBurney
- ^ "Charles L. Hamblin: Computer Pioneer" by Peter McBurney, July 27, 2008. "Hamblin soon became aware of the problems of (a) computing mathematical formulae containing brackets, and (b) the memory overhead in having dealing with memory stores each of which had its own name. One solution to the first problem was Jan Lukasiewicz's Polish notation, which enables a writer of mathematical notation to instruct a reader the order in which to execute the operations (e.g. addition, multiplication, etc) without using brackets. Polish notation achieves this by having an operator (+, *, etc) precede the operands to which it applies, e.g., +ab, instead of the usual, a+b. Hamblin, with his training in formal logic, knew of Lukasiewicz's work."
- ^ "As was demonstrated in the Algebraic mode, it is usually easier (fewer keystrokes) in working a problem like this to begin with the arithmetic operations inside the parentheses first."[1]
參見
參考
- RPN or DAL? A brief analysis of Reverse Polish Notation against Direct Algebraic Logic – By James Redin
- Postfix Notation Mini-Lecture – By Bob Brown
- Fith: An Alien Conlang With A LIFO Grammar – By Jeffrey Henning
- Good Ideas, Through the Looking Glass - By Nick Wurth