中序轉後序、前序
[後序式]
括號法,將運算子兩旁的運算元依先後順序(由左至右)全部括號起來,然後將所有的右括號取代為左邊最接近的運算子(由最內層括號開始),最後去掉所有的左括號就可以完成後序表示式,例如:
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.運算式讀取完畢,『堆疊』頂端即為答案。
中序轉後序
Infix由左往右、Postfix由左往右輸出
中序轉前序
infix由右往左、輸出Prefix也是由右往左。