moea_joint_essay
105年
[資訊] 資訊管理、程式設計
第 二 題
📖 題組：
請依算術運算式(((9+1)*3)/((7-6)+5))-((2*(3-2))+1)，回答下列問題：
請依算術運算式(((9+1)*3)/((7-6)+5))-((2*(3-2))+1)，回答下列問題：
📝 此題為申論題，共 4 小題
小題 (二)
為求得運算式之值，可採「中序(infix)」、「前序(prefix)」或「後序(postfix)」等表示法，請從記憶體耗用、程式複雜度觀點，比較此3種表示法何者較佳？為什麼？（6分）
思路引導 VIP
分析三種表示法在電腦運算時的差異。中序需要考慮括號與運算子優先級；前後序則無須括號。指出在編譯器與堆疊實作中，後序最容易實作且複雜度最低。
小題 (一)
請繪出此算術運算式之二元樹，其終端節點均為運算元（1、2、3、5、..），非終端節點均為運算子（+、-、*、/）。（5 分）
思路引導 VIP
找出最外層運算子為根節點，逐步拆解算式。最外層為中央的減號 '-'。左子樹為 (((9+1)3)/((7-6)+5))，右子樹為 ((2(3-2))+1)。依此邏輯遞迴畫出二元樹。
小題 (三)
請將此運算式，改為後序表示法(postfix expression)。（5 分）
思路引導 VIP
根據運算式樹的後序遍歷 (左-右-根)，將中序轉換為後序。左邊：9 1 + 3 * 7 6 - 5 + /。右邊：2 3 2 - * 1 +。整體合併加減號。
小題 (四)
欲使用堆疊(stack)來求得此算術運算式之解，請畫出該堆疊的資料歷程變化。（6 分）
思路引導 VIP
按照後序表示法，一步一步顯示推入和彈出堆疊的狀態。並算出最終結果 ( (103)/(1+5) - (21+1) = 30/6 - 3 = 5 - 3 = 2 )。