參考：前綴、中綴、后綴表達式(逆波蘭表達式) - chensongxian - 博客園

中綴表達式就是人們?nèi)粘Ｉ钪衅毡槭褂玫乃膭t運算表達式。如（3+4）*5

前綴表達式又稱波蘭表達式，其運算符位于操作數(shù)之前，比如:- × + 3 4 5 6

后綴表達式又稱逆波蘭表達式，其運算符位于操作數(shù)之后，比如:3 4 + 5 × 6 -

前綴表達式的計算機求值：

從右往左掃描表達式，遇到數(shù)字將其壓入棧，遇到運算符，彈出兩個數(shù)字元素并計算，然后將所求的得值壓入棧，繼續(xù)重復操作，直至只剩下一個元素，彈出，即為結果。

例如：- * + 3 4 5 6

1.掃到6，將其壓入，5壓入，4壓入，3壓入。

2.掃到+，彈出3和4，計算3+4求得7，將7壓入。

3.繼續(xù)掃，掃到*，彈出7和5，計算7*5，求得35，壓入35.

4.掃到-，彈出35和6，計算35-6，求得29，得到結果。

中綴轉(zhuǎn)前綴：

1.建立兩個棧，s1，s2，一個存放運算符，一個存放數(shù)字。

2.從右往左掃描中綴表達式，如果是數(shù)字就壓入s2。

3.若是運算符：

如果棧為空或是棧頂元素為‘（’，直接壓入運算符。

如果是‘）’，彈出并壓入s2中，直到‘（’，并且丟棄括號。

如果運算符的優(yōu)先等級大于或相等棧頂元素的優(yōu)先等級，直接壓入s1。

如果小于，則將棧頂元素彈出壓入s2，再將運算符與此時的棧頂元素相比較，若大于或相等則壓入。

4.重復操作，直至到達最左端。

5.將s1的元素依次彈出并壓入s2，依次彈出s2的元素。

后綴表達式的計算機求值：

與前綴表達式相同，只不過是從左往右。

例如計算3 4 + 5 * 6 -：

1.掃到3，壓入，4壓入。

2.掃到+，彈出3和4，計算3+4，得出7壓入。

3.掃到5，壓入。

4.掃到*，彈出5和7，計算5*7，得出35，壓入。

5.掃到6，壓入。

6.掃到-，彈出35和6，計算35-6，得出29，求出結果。

中綴轉(zhuǎn)后綴表達式：

1.建立兩個棧，s1，s2，一個存放運算符，一個存放數(shù)字。

2.從左到右掃描中綴表達式，掃到數(shù)字就壓入s2。

3.掃到運算符:

若棧為空或棧頂元素為‘（’，直接壓入s1。

若為‘）’，彈出并壓入到s2，直到‘）’，丟棄括號。

若運算符優(yōu)先級大于此時的棧頂元素，直接壓入s1。

若小于，將棧頂元素彈出壓入s2，再與新的棧頂元素比較。

4.重復，直到最右邊。

5.依次彈出s2，再逆序輸出，即為所求。