逆波蘭表達式

邏輯提問式類似於算術表達式，對於檢索而言，這種表達式並不是最優和最簡潔的形式，需要進行必要的轉換。1929年波蘭的邏輯學家盧卡西維茲(Jan Lucasiewicz)提出了將運算符放在運算項後面的邏輯表達式，又稱“逆波蘭表達式”。採用這種表達式組織邏輯提問式非常方便檢索運算，是日本的福島先生最早將逆波蘭表達式應用於情報檢索的，故又稱為“福島方法”。 ^[2] 

逆波蘭表達式又叫做後綴表達式，是一種沒有括號，並嚴格遵循“從左到右”運算的後綴式表達方法，如下表所示：

1、首先構造一個運算符棧，此運算符在棧內遵循越往棧頂優先級越高的原則。

2、讀入一個用中綴表示的簡單算術表達式，為方便起見，設該簡單算術表達式的右端多加上了優先級最低的特殊符號“#”。

3、從左至右掃描該算術表達式，從第一個字符開始判斷，如果該字符是數字，則分析到該數字串的結束並將該數字串直接輸出。

4、如果不是數字，該字符則是運算符，此時需比較優先關係。

具體做法是：將該字符與運算符棧頂的運算符的優先關係相比較。如果該字符優先關係高於此運算符棧頂的運算符，則將該運算符入棧。若不是的話，則將棧頂的運算符從棧中彈出，直到棧項運算符的優先級低於當前運算符，將該字符入棧。

5、重複步驟1～2，直至掃描完整個簡單算術表達式，確定所有字符都得到正確處理，便可以將中綴式表示的簡單算術表達式轉化為逆波蘭表示的簡單算術表達式。

逆波蘭表達式生成的算法框圖見下圖： ^[3] 

逆波蘭表達式是一種十分有用的表達式，它將複雜表達式轉換為可以依靠簡單的操作得到計算結果的表達式。例如(a+b)*(c+d)轉換為ab+cd+*。

它的優勢在於只用兩種簡單操作，入棧和出棧就可以搞定任何普通表達式的運算。其運算方式如下：

如果當前字符為變量或者為數字，則壓棧，如果是運算符，則將棧頂兩個元素彈出作相應運算，結果再入棧，最後當表達式掃描完後，棧裏的就是結果。