【筆記】前序式、中序式與後序式

發布於 更新於 分類於 閱讀次數： 文章字數： 572 所需閱讀時間 ≈ 2 分鐘

電腦怎麼進行四則運算？

電腦其實很笨，所以計算機在做運算時，只會依你的命令順序做運算。

比如題目為 3 + 2 * 4

若照著順序按，得到的答案是 20。但以四則運算來說這很明顯已經錯了，答案應該為 11。

那前中後序的差別就是運算子的先後順序，可電腦有更好的方法進行四則運算，那就是後（前）序式。

後序式如：3 2 4 * +

數字在前，而運算子在後。在中序轉後序時，運算子會在過程中有比對先後順序，而非直接把運算式按順序放置後方。

1
2
3
運算子 數字 數字  // 前序
數字 運算子 數字  // 中序
數字 數字 運算子  // 後序

所以如果要讓電腦看得懂四則運算的規則必須要讓電腦知道每個符號的有先順序
如：
* / 大於 + -
( ) 大於 * /

中序式轉後序式

若遇到數字則直接輸出或放入字串，遇到運算子就判斷後放進 stack 裡。
若 stack.top() 的運算子權重小於讀取的運算子，如：+ - 小於 * / 直接 stack.push(運算子)，
若 stack.top() 的運算子權重大於讀取的運算子，如：* / 大於 + - 則先輸出或放入字串 stack.top()，再 stack.pop()，最後才 stack.push(運算子)。
若符號是 ( 則直接放入，繼續進行程式直到遇到 )，才把 stack 到 ( 裡的符號輸出或放入字串，記得最後也要把 ( pop 掉。

中序式元素 stack 後序式
( ( 無
3 ( 3
+ (+ 3
2 (+ 32
) 32+
* * 32+
( *( 32+
4 *( 32+4
- *(- 32+4
1 *(- 32+41
) * 32+41-
32+41-* 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int order(char sy) {
    if (sy == '+' || sy == '-') {
        return 1;
    } else if (sy == '*' || sy == '/') {
        return 2;
    } else {
        return 0;
    }
}

int main() {
    string str;

    while (cin >> str) {
        stack<char> symbol;   // stack 放運算子
        string postfix = "";  // 後序式

        for (int i = 0; str[i] != '\0'; i++) {
            if (str[i] == '(') {  // 符號處理
                symbol.push('(');
            } else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/') {
                if (symbol.empty()) {
                    symbol.push(str[i]);
                } else {
                    int a = order(symbol.top()), b = order(str[i]);
                    // 若 a 是 *, b 是 -, 則權重大的先放進後序式
                    while (a >= b) {
                        postfix.push_back(symbol.top());
                        symbol.pop();
                        if (symbol.empty()) break;
                    }
                    symbol.push(str[i]);
                }
            } else if (str[i] == ')') {
                while (symbol.top() != '(') {
                    postfix.push_back(symbol.top());
                    symbol.pop();
                }
                symbol.pop();
            } else {  // 數字處裡
                postfix.push_back(str[i]);
            }
        }
        // 將未拿出的符號提出
        while (!symbol.empty()) {
            postfix.push_back(symbol.top());
            symbol.pop();
        }
        // 後序式輸出
        cout << postfix << "\n";
    }
    return 0;
}