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