Re: [課業] 資料結構 作業二

[yantchen (球童Yanting)]

中序轉前序或後序

手算很簡單

依序加上括號

然後把運算符號挪到括號前面

再把括號全部吃掉

例如

1+2*3  →  (1+(2*3)) → +1*23

寫程式的話

用括號會很複雜 ( 也不是不能做喔 )

通常會改用堆疊的方式

下面是參考答案  請用自己的話改寫 不要大家都交一樣的答案XD 

-

中序運算式轉前序運算式的演算法

1. 由右往左讀取運算式字串

2. 遇到 運算元(數字)           → 直接輸出

   遇到 運算子(符號) 和 右括號 → 判斷堆疊頂端的運算子和目前運算子的優先順序

                                      >  如果比目前的高

                                             → 先彈出，再把目前運算子壓入堆疊

                                      >  如果比目前的低或一樣

                                             → 直接將目前運算子壓入堆疊

   遇到 左括號                 → 將堆疊中的運算子彈出並輸出，到右括號為止

3. 重複步驟2，到整個運算式讀取結束

4. 如果堆疊不是空的，彈出堆疊中剩下的運算元

5. 將輸出的字串反轉，就是前序運算式

-

用上面的例子做一次

1+2*3

由右往左讀

3*2+1

                       堆疊          輸出
                    -----------   -----------

3 → 數字輸出 3                     3

* → 符號 壓入堆疊   *

2 → 數字輸出 2      *              3 2

+ → 符號 壓入堆疊   +              3 2 *     ( 因為 * 比 + 高 先彈出 )

1 → 數字輸出 1      +              3 2 * 1

清空堆疊                            3 2 * 1 +

反轉結果                            + 1 * 2 3  # ok


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.36.97.131
推 jerry771210:有沒有中序轉後序的 組語版XD
→ yantchen:組語做堆疊還蠻痛苦的XD
→ yantchen:去年只有排序跟求值耶 今年好狠
推 j2612280:哇嗚=0=
→ yantchen:組語的在這裡
http://home.educities.edu.tw/wanker742126/win32asm/w32asm_ap02.html
※ 編輯: yantchen        來自: 203.68.15.196        (10/26 18:20)

噢 前面的 運算子 跟 運算元 打反了 後面條件寫運算子是對的 前面居然寫反XD
※ 編輯: yantchen        來自: 203.68.15.196        (11/02 15:12)