逆波蘭表示法

逆波蘭表示法（英語：Reverse Polish notation，縮寫RPN，或逆波蘭記法、逆盧卡西維茨記法），是一種由波蘭數學家揚·盧卡西維茨於1920年引入的數學表達式形式，在逆波蘭記法中，所有運算子置於運算元的後面，因此也被稱為字尾表示法、後序表示法^[1]。逆波蘭記法不需要括號來標識運算子的優先級。

影片：在 1991 年 Hewlett-Packard HP-32SII 上鍵入按鍵序列來計算八乘六

逆波蘭結構由弗里德里希·L·鮑爾（英語：Friedrich L. Bauer）和艾茲格·迪科斯徹在1960年代早期提議用於表達式求值，以利用堆疊結構減少電腦主記憶體訪問。逆波蘭記法和相應的演算法由澳大利亞哲學家、電腦學家查爾斯·倫納德·漢布林（英語：Charles Leonard Hamblin）在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，等都是用了逆波蘭表達式。

實際意義

• 當有運算子時就計算，因此，表達式並不是從右至左整體計算而是每次由中心向外計算一部分，這樣在複雜運算中就很少導致運算子錯誤。
• 堆疊自動記錄中間結果，這就是為什麼逆波蘭計數機能容易對任意複雜的表達式求值。與普通科學計數機不同，它對表達式的複雜性沒有限制。
• 逆波蘭表達式中不需要括號，用戶只需按照表達式順序求值，讓堆疊自動記錄中間結果；同樣的，也不需要指定運算子的優先級。
• 逆波蘭計數機中，沒有「等號」鍵用於開始計算。
• 逆波蘭計數機需要「確認」鍵用於區分兩個相鄰的運算元。
• 機器狀態永遠是一個堆疊狀態，堆疊里是需要運算的運算元，棧內不會有運算子。
• 教育意義上，逆波蘭計數機的用戶必須懂得要計算的表達式的含義。

目前逆波蘭的實現有：

• 任何基於棧的程式語言：
  • Forth
  • Factor
  • PostScript語言。
• 線上的逆波蘭計數機
• 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