作者yantchen (球童Yanting)
看板NTUE-CS101
標題Re: [課業] 資料結構 作業二
時間Sun Oct 25 17:06:38 2009
中序轉前序或後序
手算很簡單
依序加上括號
然後把運算符號挪到括號前面
再把括號全部吃掉
例如
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
1F：推 jerry771210:有沒有中序轉後序的 組語版XD 10/25 18:05
2F：→ yantchen:組語做堆疊還蠻痛苦的XD 10/25 18:05
3F：→ yantchen:去年只有排序跟求值耶 今年好狠 10/25 18:06
4F：推 j2612280:哇嗚=0= 10/25 19:38
5F：→ yantchen:組語的在這裡 10/26 18:20
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)