中序轉後序、前序

[後序式]

括號法，將運算子兩旁的運算元依先後順序(由左至右)全部括號起來，然後將所有的右括號取代為左邊最接近的運算子（由最內層括號開始），最後去掉所有的左括號就可以完成後序表示式，例如：

a+b*d+c/d => ((a+(b*d))+(c/d)) -> abd*+cd/+

[演算法]

由左至右掃描中序運算式：

一、運算元：直接輸出至postfix。

二、運算子與左括號：堆疊中運算子優先順序>=讀入的運算子，則輸出堆疊中的運算子、再將讀入的運算子置入堆疊，否則將讀入的運算子置入堆疊。

三、右括號：輸出堆疊中的運算子，直至遇見堆疊中的左括號。

輸出時也是由左至右。

[計算步驟]

參考網址：https://openhome.cc/Gossip/AlgorithmGossip/PostfixCal.htm

1.由後序式的前方開始讀取。

2.遇「運算元」先存入『堆疊』。

3.遇「運算子」，則由堆疊取出兩個「運算元」進行運算，將結果存回『堆疊』。

4.運算式讀取完畢，『堆疊』頂端即為答案。

[前序式]

括號法，將運算子兩旁的運算元依先後順序(由右至左)全部括號起來，然後將所有的左括號取代為右邊最接近的運算子（由最內層括號開始），最後去掉所有的右括號就可以完成後序表示式，例如：

a+b*d+c/d => ((a+(b*d))+(c/d)) -> ++a*bd/cd

[演算法]

由右至左掃描中序運算式：

一、運算元：直接輸出至prefix。

二、運算子與右括號：堆疊中運算子優先順序>=讀入的運算子，則輸出堆疊中的運算子、再將讀入的運算子置入堆疊，否則將讀入的運算子置入堆疊。

三、左括號：輸出堆疊中的運算子，直至遇見堆疊中的右括號。

輸出時也是由右至左。

[計算步驟]

1.一樣由前序式的前方開始讀取。

2.遇「運算元」先存入『堆疊』。

3.遇「運算子」，則由堆疊取出兩個「運算元」進行運算，將結果存回『堆疊』。

※傳入的運算元次序與後序式相反。※

4.運算式讀取完畢，『堆疊』頂端即為答案。

參考文獻

https://magiclen.org/arithmetic/