算術表達式的前綴表達式，中綴表達式和后綴表達式

這里所謂的前綴，中綴，后綴是根據操作符的位置來定的，如果操作符在操作數前面，則稱為前綴表達式，例如“- + 1 × + 2 3 4 5”;如果操作符在操作數之間，則稱為中綴表達式，例如

“1+((2+3)×4)-5”;如果操作符在操作數后面，則稱為后綴表達式，例如“1 2 3 + 4 × + 5 -”。

雖然中綴表達式符合人類的日常思維習慣，但是計算機在存儲中綴表達式時，需要使用樹這種數據結構，如果表達式過于復雜，那么樹的高度會變得很高，大大增加了時間復雜度和空間復雜度。如果轉換成線性結構，那么效率將變得高很多，所以需要將中綴表達式先轉換成前綴或者后綴表達式，然后依靠棧這種線性數據結構來進行計算。

前綴表達式又叫波蘭表達式，后綴表達式又叫逆波蘭表達式。前綴表達式基本沒有在商業計算機中使用過，所以現實中用的更多的是后綴表達式。

如何將中綴表達式轉化成后綴表達式呢？

利用兩個棧S1，S2：其中S1存放操作符，S2存放操作數

從左往右遍歷中綴表達式，如果遇到數字，則放入S2中，如果遇到操作符，則放入S1中。在放操作符的時候有一定的規則，如果棧為空或棧頂元素為（，則直接壓棧。如果是(，也直接壓棧;如果棧頂元素為普通操作符，則比較優先級，如果待壓棧的操作符比棧頂操作符優先級高，則直接壓棧，否則將S1中的棧頂元素出棧，并壓入S2中，再接著比較S1棧頂元素的優先級。如果遇到)，則依次彈出S1棧頂的運算符，并壓入S2，直到遇到左括號為止，此時將這一對括號丟棄。最后將S1中剩余的運算符依次彈出并壓入S2，逆序輸出S2（從棧底到棧頂）便得到了后綴表達式。（注意：等號的優先級最低，因為要到最后才進行賦值操作）

得到后綴表達式之后，計算就變得方便多了，遇到數字就壓棧，遇到操作符的時候，pop出棧頂的兩個元素，進行計算后將結果又壓入棧中，這樣一直下去，直到得到最終結果。

將中綴表達式“1+((2+3)×4)-5”轉換為后綴表達式的過程如下：

結果為“1 2 3 + 4 × + 5 -”（需要逆序輸出）