題組內容

三、A*( B + C) - D / E 為中序（Infix）表示式。

⑵請用適當的資料結構，以繪圖（或表）與使用文字說明中序轉後序演算過程。 （10 分）

詳解 (共 2 筆)

詳解 提供者：Lu_yee
中序式A*(B+C)-D/E
後序式指把符號往後擺，先自行設立左右括號 ((A*(B+C))-(D/E))，當遇到右括號時把符號擺進去。
ABC遇到第一個右括弧，把優先權較高(括號優先權高於乘法)的符號擺進去”+”第二個右括弧擺上”*”，繼續擺放DE直到遇上第三個右括弧擺放”/”，最後擺放”-”
因此後序式為 ABC+*DE/-
詳解 提供者：hchungw
 
 
 
轉換結果
最後的後序（Postfix）表示式為：
 
ABC+*DE/-
 

總結
在此過程中，我們使用堆疊暫存運算符，並按照運算符優先級和括號的規則處理，最終生成後序表示式。此方法高效且易於實現，廣泛應用於編譯器和表達式求值中。

轉換過程中，我們使用堆疊來暫存運算符並按順序輸出操作數。這裡我們用 A∗(B+C)−D/EA*(B + C) - D / EA∗(B+C)−D/E 作為範例進行演示。

資料結構和步驟

  1. 初始化：

    • 輸入：A∗(B+C)−D/EA*(B + C) - D / EA∗(B+C)−D/E
    • 輸出：空
    • 堆疊：空

  2. 讀取並處理每個字符：

    • 遇到操作數：直接輸出
    • 遇到左括號：推入堆疊
    • 遇到右括號：彈出堆疊直到遇到左括號
    • 遇到運算符：根據優先級處理，若堆疊頂端運算符優先級高或相等則彈出，否則推入堆疊

演算過程

步驟 輸入 堆疊 輸出 操作說明
1 AAA [] AAA 直接輸出操作數 AAA
2 ∗*∗ [*] AAA 遇到運算符 ∗*∗，推入堆疊
3 ((( [*, (] AAA 遇到左括號，推入堆疊
4 BBB [*, (] ABABAB 直接輸出操作數 BBB
5 +++ [*, (, +] ABABAB 遇到運算符 +++，推入堆疊
6 CCC [*, (, +] ABCABCABC 直接輸出操作數 CCC
7 ))) [*] ABC+ABC+ABC+ 遇到右括號，彈出堆疊直到左括號，左括號丟棄
8 −-− [-] ABC+∗ABC+*ABC+∗ 遇到運算符 −-−，與堆疊頂運算符∗*∗ 比較優先級，∗*∗ 優先級較高，先彈出，再推入 −-−
9 DDD [-] ABC+∗DABC+*DABC+∗D 直接輸出操作數 DDD
10 /// [-, /] ABC+∗DABC+*DABC+∗D 遇到運算符 ///，推入堆疊
11 EEE [-, /] ABC+∗DEABC+*DEABC+∗DE 直接輸出操作數 EEE
12   [] ABC+∗DE/−ABC+*DE/-ABC+∗DE/−
輸入處理完畢，依次彈出堆疊並輸出