逆波蘭表示法

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書
前綴表示法 （+ 3 4 ）
中綴表示法 （3 + 4）
後綴表示法 （3 4 + ）

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

逆波蘭結構由弗里德里希·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，等都是用了逆波蘭表達式。

實際意義[編輯]

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

目前逆波蘭的實現有：

注釋[編輯]

  1. ^ 課程名稱：程式設計 - 中序轉後序、前序. sites.google.com. [2022-08-22]. （原始內容存檔於2022-08-22） （中文（中國大陸））. 
  2. ^ "Charles L. Hamblin and his work" 網際網路檔案館的存檔，存檔日期2008-12-06. by Peter McBurney
  3. ^ "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."
  4. ^ "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] （頁面存檔備份，存於網際網路檔案館）

參見[編輯]

參考[編輯]

取自「https://zh.wikipedia.org/w/index.php?title=逆波兰表示法&oldid=79191349」