?一、算術表達式的中綴表示
把運算符放在參與運算的兩個操作數中間的算術表達式稱為中綴表達式。例如：2+3*4 - 6/9
算術表達式中包含了算術運算符和算術量(常量、變量、函數)，而運算符之間又存在著優先級，不能簡單地進行從左到右運算，編譯程序在求值時，不能簡單從左到右運算，必須先算運算級別高的，再算運算級別低的，同一級運算才從左到右。在計算機中進行中綴表達式求值較麻煩。而后綴表達式求值較方便（無須考慮運算符的優先級及圓括號）。
???
??? 二、算術表達式的后綴表示
把運算符放在參與運算的兩個操作數后面的算術表達式稱為后綴表達式。
例如，對于下列各中綴表達式：
(1)3/5+8
(2)18-9*(4+3)
對應的后綴表達式為：
(1)3 5 / 8 +
(2)18 9 4 3 + * -
轉換規則:把每個運算符都移到它的兩個操作數的后面,然后刪除掉所有的括號即可.
??? 三 表達式的計算：
由于后綴表達式中沒有括號，不需判別優先級，計算嚴格從左向右進行，故計算一個后綴表達式要比計算機一個中綴表達式簡單得多。
將中綴表達式轉換為后綴表達式的算法思想：
·當讀到數字直接送至輸出隊列中
·當讀到運算符t時，
a.將棧中所有優先級高于或等于t的運算符彈出，送到輸出隊列中；
b.t進棧
·讀到左括號時總是將它壓入棧中
·讀到右括號時，將靠近棧頂的第一個左括號上面的運算符全部依次彈出，送至輸出隊列后，再丟棄左括號。
??? 中綴表達式全部讀完后，若棧中仍有運算符，將其送到輸出隊列中
運用后綴表達式進行計算的具體做法：
·建立一個棧S
·從左到右讀后綴表達式，讀到數字就將它轉換為數值壓入棧S中，讀到運算符則從棧中依次彈出兩個數分別到Y和X，然后以"X 運算符 Y"的形式計算機出結果，再壓加棧S中
·如果后綴表達式未讀完，就重復上面過程，最后輸出棧頂的數值則為結束
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=619852