逆波蘭表達式又叫做后綴表達式，它將復雜表達式轉換為可以依靠簡單的操作得到計算結果的表達式，解決了四則運算中括號改變運算符優先級的問題。
四則運算的表達式一般都是中綴表達式如 1+2*(3-4)+5，即操作符在兩個操作數之間。四則運算需要兩個步驟，一是把中綴表達式轉為后綴表達式，二是由后綴表達生成結果
中綴表達式轉為后綴表達式算法描述：
(1)首先有個包含中綴表達式元素列表sourceList,然后創建一個符號列表destList保存最終后綴表達式,創建一個操作符堆棧opStack
(2)從sourceList取出一個元素A
(3a)如是數字則加入到destList中
(3b)如果元素A是運算符，將操作符A與操作符堆棧opStack棧頂的運算符的優先關系相比較。如果，優先關系高于opStack棧頂的運算符，則將該運算符壓入操作符堆棧opStack。倘若不是(低于或等于)的話，則將運算符棧opStack棧頂的運算符從棧中彈出保存到destList，重復此步驟,直到作符A壓入操作符堆棧opStack。
(3c)若元素A是左括號"("，則壓入操作符堆棧opStack
(3d)若元素B是右括號")",則操作符堆棧opStack彈出操作符并加入到destList中，直到彈出左括號"("。
(5)從步驟2重復上述操作，所有元素處理完畢后將操作符堆棧opStack彈出操作符并加入到destList中，這樣中綴式表示的簡單算術表達式轉化為逆波蘭表示的簡單算術表達式。
示例：
中綴表達式如 1+2*(3-4)+5，構造元素列表1,+,2,*,(,3,-,4,),5,構造一個空最終后綴表達式destList，一個操作符堆棧opStack
1、取出“1”，destList【1】，opStack【】
2、取出“+”，destList【1】，opStack【+】
3、取出“2”，destList【1,2】，opStack【+】
4、取出“*”，destList【1,2】，opStack【+,*】
5、取出“(”，destList【1,2】，opStack【+,*,(】
6、取出“3”，destList【1,2,3】，opStack【+,*,(】
7、取出“-”，destList【1,2,3】，opStack【+,*,(,-】
8、取出“4”，destList【1,2,3,4】，opStack【+,*,(,-】
9、取出“)”，destList【1,2,3,4,-】，opStack【+,*】 //操作符堆棧opStack彈出操作符并加入到destList中，直到彈出左括號"("
10、取出“+”，destList【1,2,3,4,-,*,+】，opStack【+】 //加號優先級不大于【+,*】
11、取出“5”，destList【1,2,3,4,-,*,+,5】，opStack【+】
12、處理完畢，destList【1,2,3,4,-,*,+,5,+】，opStack【】
后綴表達式到計算結果算法描述：
遍歷儲存后綴表達式的列表，將元素依次進棧，當遇到操作符時，連續出棧兩個元素，進行運算，再將結果進棧，最后棧內留下的元素就是計算結果
示例：
后綴表達式destList【1,2,3,4,-,*,+,5,+】，結果堆棧resultStatck【】
格式
輸入-->:結果
[1,2,3,4]-->:resultStatck【1,2,3,4】
[-]-->:resultStatck【1,2,3-4】
[ * ]-->:resultStatck【1,2*(3-4)】
[+]-->:resultStatck【1+2*(3-4)】
[5]-->:resultStatck【1+2*(3-4),5】
[+]-->:resultStatck【1+2*(3-4)+5】
已有 0 人發表留言，猛擊->>這里<<-參與討論
ITeye推薦