逆波蘭表示法

<image>

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

逆波蘭結構由弗里德里希·L·鮑爾和艾茲格·迪科斯徹在1960年代早期提議用於表達式求值，以利用堆棧結構減少電腦記憶體訪問。逆波蘭記法和相應的演算法由澳大利亞哲學家、電腦學家查爾斯·倫納德·漢布林在1960年代中期擴充。

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

下面大部分是關於二元運算，一個一元運算使用逆波蘭記法的例子是階乘的記法。

## 解釋

逆波蘭記法中，操作符置於操作數的後面。例如表達「三加四」時，寫作「逆」，而不是「3 + 4」。如果有多個操作符，操作符置於第二個操作數的後面，所以常規中綴記法的「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｜入棧｜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++程序實現

```cpp
#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的逆波蘭計算器）：

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
- Unix下的計算程序dc
- Factor
- PostScript語言。
- 線上的逆波蘭計算器
- Windows下逆波蘭計算器
- Windows XP下的Microsoft PowerToy calculator
- 手機逆波蘭計算器，開源的JAVA計算器
- Palm PDA下的逆波蘭計算器
- Mac OS X計算器
- Mac OS X和iPhone下的逆波蘭計算器
- 交互式JavaScript的逆波蘭計算器
- calculations(Ada語言中的逆波蘭計算器)
- Emacs的lisp lib包: calc
- 基於GTK+的galculator
- 表達式轉換

## 參考

- 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