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