逆波蘭表達式又叫做後綴表達式。逆波蘭表示法是波蘭邏輯學家J・盧卡西維茲(J・ Lukasewicz)於1929年首先提出的一種表達式的表示方法。後來,人們就把用這種表示法寫出的表達式稱作“逆波蘭表達式”。逆波蘭表達式把運算量寫在前面,把算符寫在後面。
基本介紹
- 中文名：逆波蘭表達式
- 外文名：Reverse Polish Notation
- 別名：後綴表達式
- 提出者：盧卡西維茲
- 時間：1929年
- 套用領域：數理科學
定義,算法步驟,算法框圖,用途,優勢,
定義
邏輯提問式類似於算術表達式，對於檢索而言，這種表達式並不是最優和最簡潔的形式，需要進行必要的轉換。1929年波蘭的邏輯學家盧卡西維茲(Jan Lucasiewicz)提出了將運算符放在運算項後面的邏輯表達式，又稱“逆波蘭表達式”。採用這種表達式組織邏輯提問式非常方便檢索運算，是日本的福島先生最早將逆波蘭表達式套用於情報檢索的，故又稱為“福島方法”。
逆波蘭表達式又叫做後綴表達式，是一種沒有括弧，並嚴格遵循“從左到右”運算的後綴式表達方法，如下表所示：
算法步驟
1、首先構造一個運算符棧，此運算符在棧內遵循越往棧頂優先權越高的原則。
2、讀入一個用中綴表示的簡單算術表達式，為方便起見，設該簡單算術表達式的右端多加上了優先權最低的特殊符號“#”。
3、從左至右掃描該算術表達式，從第一個字元開始判斷，如果該字元是數字，則分析到該數字串的結束並將該數字串直接輸出。
4、如果不是數字，該字元則是運算符，此時需比較優先關係。
具體做法是：將該字元與運算符棧頂的運算符的優先關係相比較。如果該字元優先關係高於此運算符棧頂的運算符，則將該運算符入棧。若不是的話，則將棧頂的運算符從棧中彈出，直到棧項運算符的優先權低於當前運算符，將該字元入棧。
5、重複步驟1～2，直至掃描完整個簡單算術表達式，確定所有字元都得到正確處理，便可以將中綴式表示的簡單算術表達式轉化為逆波蘭表示的簡單算術表達式。
算法框圖
逆波蘭表達式生成的算法框圖見下圖：
用途
逆波蘭表達式是一種十分有用的表達式，它將複雜表達式轉換為可以依靠簡單的操作得到計算結果的表達式。例如(a+b)*(c+d)轉換為ab+cd+*。
優勢
它的優勢在於只用兩種簡單操作，入棧和出棧就可以搞定任何普通表達式的運算。其運算方式如下：
如果當前字元為變數或者為數字，則壓棧，如果是運算符，則將棧頂兩個元素彈出作相應運算，結果再入棧，最後當表達式掃描完後，棧里的就是結果。
