|
中序轉前序演算法 (設前序式字串為 prefix)
步驟：
| 1. | 讀取運算式 1 個字元。 |
| 2. |
| A. | 若是運算元，則直接輸出至 prefix。 |
| B. | 若是右括號 )，則直接推入堆疊。 |
| C. | 若是左括號 (，則從堆疊取出運算子至 prefix，直到右括號被取出為止。 |
| D. | 若是運算子，
- 若堆疊為空，直接推入堆疊。
- 若運算子優先度小於堆疊內運算子，則取出堆疊內所有小於的運算子至 prefix，然後再將運算子推入堆疊。(右括號 ) 優先度最低)
- 否則運算子直接推入堆疊。
|
|
| 3. | 若運算式字串未讀完重複步驟 1。 |
| 4. | 將堆疊內所有運算子取出至 prefix。 |
中序 5*(3-8/4)-2 轉前序範例
| 算式 |
讀取1字 |
堆疊 |
postfix |
規則 |
| 5*(3-8/4)-2 | 2 | | 2 | 2.A |
| 5*(3-8/4)-2 | - | - | 2 | 2.D.1 |
| 5*(3-8/4)-2 | ) | )
-
| 2 | 2.B |
| 5*(3-8/4)-2 | 4 | )
- | 42 | 2.A |
| 5*(3-8/4)-2 | / | /
)
- | 42 | 2.D.3 |
| 5*(3-8/4)-2 | 8 | /
)
- | 842 | 2.A |
| 5*(3-8/4)-2 | - | -
)
- | /842 | 2.D.2 |
| 5*(3-8/4)-2 | 3 | -
)
- | 3/842 | 2.A |
| 5*(3-8/4)-2 | ( | - | -3/842 | 2.C |
| 5*(3-8/4)-2 | * | *
- | -3/842 | 2.D.3 |
| 5*(3-8/4)-2 | 5 | *
- | 5-3/842 | 2.A |
| | | | -*5-3/842 | 4 |
前序式求值
步驟：
| 1. | 從後面讀取運算式 1 個字元。 |
| 2. |
| A. | 若是運算元，則將運算元推入堆疊。 |
| B. | 若是運算子，則取出堆疊運算元置於運算子左方，再取出堆疊運算元置於運算子右方。經計算後將結果推入堆疊。 |
|
| 3. | 若運算式字串未讀完重複步驟 1。 |
| 4. | 堆疊內的資料為運算式結果。 |
範例：-+23/*584 (原中序式為 2+3-5*8/4)
| 步驟 | 運算式讀取字元 | 堆疊內容 | 運算結果 |
| 1 | -+23/*584 | | |
| 2 | -+23/*58 | 4 | |
| 3 | -+23/*5 | 8
4 | 2+3=5 |
| 4 | -+23/* | 5
8
4 | 5*8=40 |
| 5 | -+23/ | 40
4 | 40/4=10 |
| 6 | -+23 | 10 | |
| 7 | -+2 | 3
10 | |
| 8 | -+ | 2
3
10 | 2+3=5 |
| 8 | - | 5
10 | 5-10=-5 |
| 9 | 結果：-5 | -5 | |
範例：*3-9*76 (原中序式為 3*(9-7*6))
| 步驟 | 運算式讀取字元 | 堆疊內容 | 運算結果 |
| 1 | *3-9*76 | | |
| 2 | *3-9*7 | 6 | |
| 3 | *3-9* | 7
6 | 7*6=42 |
| 4 | *3-9 | 42 | |
| 5 | *3- | 9
42 | 9-42=-33 |
| 6 | *3 | -33 | |
| 7 | * | 3
-33 | 3*-33=-99 |
| 8 | 結果：-99 | -99 | |
|