中序轉後序、前序

[後序式]

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

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也是由右往左。

主程式


運算優先順序