逆波蘭表示法
|
| 字首表示法 （+ 3 4 ） |
| 中綴表示法 （3 + 4） |
| 字尾表示法 （3 4 + ） |
逆波蘭表示法（英語：Reverse Polish notation，縮寫RPN，或逆波蘭記法、逆盧卡西維茨記法），是一種由波蘭數學家揚·盧卡西維茨於1920年引入的數學表達式形式，在逆波蘭記法中，所有運算子置於運算元的後面，因此也被稱為字尾表示法、後序表示法[1]。逆波蘭記法不需要括號來標識運算子的優先級。
逆波蘭結構由弗里德里希·L·鮑爾和艾茲格·迪科斯徹在1960年代早期提議用於表達式求值，以利用堆疊結構減少電腦主記憶體訪問。逆波蘭記法和相應的演算法由澳大利亞哲學家、電腦學家查爾斯·倫納德·漢布林在1960年代中期擴充[2][3]。
在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 有輸入
- 讀入下一個符號X
- IF X是一個運算元
- 入棧
- ELSE IF X是一個運算子
- 有一個先驗的表格給出該運算子需要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
C++程式實現
[編輯]#include <iostream>
#include<queue>
#include<stack>
#define ERROR 0
#define OK 1
using namespace std;
typedef int Staus;
typedef double ElemType;
bool Get_ops(stack<ElemType>* st, ElemType* op1, ElemType* op2)
{
if (st->size() < 2)
return ERROR;
*op1 = st->top();
st->pop();
*op2 = st->top();
st->pop();
return OK;
}
Staus Solve(stack<ElemType>* st, char oper)
{
bool flag = 0;
ElemType oper1, oper2;
flag = Get_ops(st, &oper1, &oper2);
if (flag)
{
switch (oper)
{
case('+'):st->push(oper2 + oper1); break;
case('-'):st->push(oper2 - oper1); break;
case('*'):st->push(oper2 * oper1); break;
case('/'):if (!oper1)
{
cout << "Divide by 0！" << endl;
return ERROR;
}
else st->push(oper2 / oper1);
break;
case('^'):st->push(pow(oper2, oper1)); break;
}
}
else return ERROR;
return OK;
}
int main()
{
stack<ElemType> suffix;
char c;
ElemType t;
c = getchar();
while (c != '#')
{
switch (c)
{
case(' '):break;
case('+'):;
case('-'):;
case('*'):;
case('/'):;
case('^'):Solve(&suffix, c); break;
default:ungetc(c, stdin);
cin >> t;
suffix.push(t);
}
c = getchar();
}
cout << suffix.top() << endl;
return 0;
}
上述運算可以重寫為如下運算鏈方法（用於HP的逆波蘭計數機）：[4]
- 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] （頁面存檔備份，存於互聯網檔案館）
- scratch
註釋
[編輯]- ^ 課程名稱：程式設計 - 中序轉後序、前序. sites.google.com. [2022-08-22]. （原始內容存檔於2022-08-22） （中文（中國大陸））.
- ^ "Charles L. Hamblin and his work" 互聯網檔案館的存檔，存檔日期2008-12-06. by Peter McBurney
- ^ "Charles L. Hamblin: Computer Pioneer" 互聯網檔案館的存檔，存檔日期2008-12-07. 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