第 二 題

以「後序(postfix)」表示法為最佳。原因如下：

1. 程式複雜度低：後序表示法去除了括號的干擾，且運算子的出現順序即為計算的先後順序。計算時只需要由左至右掃描一次（時間複雜度 O(n)），遇到運算元推入堆疊，遇到運算子即從堆疊取出兩值計算並放回，邏輯十分單純。相較之下，中序需要考慮運算子優先權及括號處理。
2. 記憶體耗用少：計算過程只需一個線性陣列所實作的堆疊 (Stack) 即可；若是前序或中序，在實作求值時常需依賴遞迴 (Recursion) 而產生遞迴呼叫堆疊 (Call Stack) 的空間開銷，或需額外儲存抽象語法樹，使得耗用的記憶體較多。

本算術運算式可切分為左半部 (((9+1)3)/((7-6)+5)) 與右半部 ((2(3-2))+1)，中間以減號相連。 二元樹結構如下： [-]

對第(一)題之二元樹進行後序走訪 (Post-order traversal: 左-右-中)： 左半部：9 1 + 3 * 7 6 - 5 + / 右半部：2 3 2 - * 1 +

後序表示法掃描順序與堆疊歷程如下 (右側為堆疊頂端)：

1. 讀 9 -> Stack: [9]
2. 讀 1 -> Stack: [9, 1]