1. 中綴表達式 和 后綴表達式

中綴表達式: 顧名思義，操作符在操作數(shù)的中間，例如: 1 + 1

后綴表達式: 指操作符在操作后后面 ，例如 1 1 + ， 就代表 中綴表達式 的 1 + 1

2. 關于數(shù)據(jù)結構: 棧

棧就是一個先進先出的隊列

C語言函數(shù)之間調用，就是使用棧進行的

3. 中綴表達式 如何利用棧 轉換為后綴表達式

利用棧轉換規(guī)則如下

遍歷中綴表達式

判斷為數(shù)字直接輸出

判斷為(入棧

判斷為)則，出棧 直至遇到(

判斷為 * 或/

4.1 判斷棧頂元素是否是 * 或/， 如果是 則出棧

4.2 若1不符合規(guī)則，再將這個字符入棧

5.1 判斷棧頂元素是否是 * 或/，如果是，則全部出棧，然后再入棧

5.2 若1不符合，再將這個字符入棧

判斷為+或-，則

若表達式計算完畢，將出棧所有數(shù)據(jù)

實際例子

通過棧，將式子3+2(9+8)/3(3/5)轉換為后綴表達式

開始式子:3+2*(9+8)/3*(3/5)

開始處理: 3
執(zhí)行規(guī)則1，是數(shù)字直接輸出

輸出:3

棧:

開始處理: +
執(zhí)行規(guī)則 5.2 直接入棧

輸出:3

棧:+

開始處理: 2
執(zhí)行規(guī)則1，是數(shù)字直接輸出

輸出:32

棧:+

開始處理: *
執(zhí)行規(guī)則4.2，直接入棧

輸出:32

棧:+*

開始處理: (
執(zhí)行規(guī)則2，直接入棧

輸出:32

棧:+*(

開始處理: 9
執(zhí)行規(guī)則1，直接入棧

輸出:329

棧:+*(

開始處理: +
執(zhí)行規(guī)則5.2，直接入棧

輸出:329

棧:+*(+

開始處理: 8
執(zhí)行規(guī)則1，直接入棧

輸出:3298

棧:+*(+

開始處理: )
執(zhí)行規(guī)則3，出棧直至遇到 (

輸出:3298+

棧:+*

開始處理: /
執(zhí)行規(guī)則4.1，將棧頂元素為*或/直接出棧，然后在入棧該操作符

輸出:3298+*

棧:+/

開始處理: 3
執(zhí)行規(guī)則1,直接入棧

輸出:3298+*3

棧:+/

開始處理: *
執(zhí)行規(guī)則4.1，將棧頂元素為*或/直接出棧，然后在入棧該操作符

輸出:3298+*3/

棧:+*

開始處理: (
執(zhí)行規(guī)則2,直接入棧

輸出:3298+*3/

棧:+*(

開始處理: 3
執(zhí)行規(guī)則1,直接入棧

輸出:3298+*3/3

棧:+*(

開始處理: /
執(zhí)行規(guī)則4.2,入棧

輸出:3298+*3/3

棧:+*(/

開始處理: 5
執(zhí)行規(guī)則1,直接入棧

輸出:3298+*3/35

棧:+*(/

開始處理: )
執(zhí)行規(guī)則3,出棧 直至遇到(

輸出:3298+*3/35/

棧:+*

開始處理: )
執(zhí)行規(guī)則6,全部出棧

輸出:3298+*3/35/*+

棧:

得到中綴表達式:3298+*3/35/*+

完畢

轉換代碼 C語言實現(xiàn):

# include 

int main() {
    // 中綴表達式
    char formula[] = "3+2*(9+8)/3*(3/5)";

    // 棧
    char options[sizeof(formula) * sizeof(char)];
    int stackLen = -1;
    
    printf("%s
",formula);

    int i;
    for (i = 0; formula[i]!='?'; i++) {
        // 規(guī)則1
        if (formula[i] >= '0' && formula[i] <= '9') {
            printf("%c",formula[i]);
        }

        switch (formula[i]) {
            // 規(guī)則2
            case '(': {
                stackLen += 1;
                options[stackLen] =formula[i];
                break;
            }

            // 規(guī)則3
            case ')': {
                while (stackLen >= 0 &&  (options[stackLen] != '(')) {
                    printf("%c",options[stackLen]);
                    stackLen -= 1;
                }
                stackLen-=1;
                break;
            }

            // 規(guī)則4
            case '*':
            case '/': {
                while (stackLen >= 0 && (options[stackLen] == '*' || options[stackLen] == '/')) {
                    printf("%c",options[stackLen]);
                    stackLen -= 1;
                }
                stackLen += 1;
                options[stackLen] = formula[i];
                break;
            }

            // 規(guī)則5
            case '+': 
            case '-': {
                if (stackLen >= 0 &&  (options[stackLen] == '*' || options[stackLen] == '/')) {
                    while (stackLen >= 0) {
                        printf("%c",options[stackLen]);
                        stackLen -= 1;
                    }
                }
                stackLen += 1;
                options[stackLen] = formula[i];
                break;
            }
        }
    }

    // 規(guī)則6 
    while (stackLen >= 0) {
        printf("%c",options[stackLen]);
        stackLen--;
    }

    printf("
");
}

執(zhí)行結果

# gcc calTest1.c
# ./a.out
3+2*(9+8)/3*(3/5)
3298+*3/35/*+
#

4. 利用棧 后綴表達式計算結果

利用棧計算后綴表達式規(guī)則如下

假設后綴表達式是有效的

遍歷后綴表達式

判斷為數(shù)字，則進行壓棧

判斷為操作符(+ - * /)

2.1 出棧2個元素，m 和 n (對于當前棧而言,m: 棧頂元素 n: 棧頂?shù)诙€元素)

2.2 計算 n操作符m ,然后將結果 入棧

實際例子

通過棧，將計算后綴表達式3298+*3/35/*+的值

式子:3298+*3/35/*+

開始處理: 3

執(zhí)行規(guī)則1: 直接入棧

棧:3

開始處理: 2

執(zhí)行規(guī)則1: 直接入棧

棧:3 2

開始處理: 9

執(zhí)行規(guī)則1: 直接入棧

棧:3 2 9

開始處理: 8

執(zhí)行規(guī)則1: 直接入棧

棧:3 2 9 8

開始處理: +

執(zhí)行規(guī)則2: 取出2個元素,m:8 n:9, 并且執(zhí)行結果（n + m）入棧

棧:3 2 17

開始處理: *

執(zhí)行規(guī)則2: 取出2個元素,m:17 n:2, 并且執(zhí)行結果(n * m)入棧

棧:3 34

開始處理: 3

執(zhí)行規(guī)則1: 直接入棧

棧:3 34 3

開始處理: /

執(zhí)行規(guī)則2: 取出2個元素,m:3 n:34, 并且執(zhí)行結果(n / m)入棧

棧:3 11.3

開始處理: 3

執(zhí)行規(guī)則1: 直接入棧

棧:3 11.3 3

開始處理: 5

執(zhí)行規(guī)則1: 直接入棧

棧:3 11.3 3 5

開始處理: /

執(zhí)行規(guī)則2: 取出2個元素,m:5 n:3, 并且執(zhí)行結果(n / m)入棧

棧:3 11.3 0.6

開始處理: *

執(zhí)行規(guī)則2: 取出2個元素,m:0.6 n:11.3, 并且執(zhí)行結果(n * m)入棧

棧:3 6.8

開始處理: +

執(zhí)行規(guī)則2: 取出2個元素,m:6.8 n:3, 并且執(zhí)行結果(n + m)入棧

棧:9.8

計算結果:9.8

完成

用C實現(xiàn)該代碼

轉換代碼 C語言實現(xiàn):

# include 

int main() {
    // 后綴表達式
    char formula[] = "3298+*3/35/*+";

    // 棧
    float options[sizeof(formula) * sizeof(char)];
    int stackLen = -1;
    
    printf("%s
",formula);

    int i;
    for(i=0;formula[i]!='?';i++) {
        // 規(guī)則1
        if (formula[i] >= '0' && formula[i] <= '9') {
            stackLen++;
            options[stackLen] = (float)(formula[i]-48);
        } else {
            // 規(guī)則2
            float m = options[stackLen];
            stackLen--;

            float n = options[stackLen];
            stackLen--;

            switch (formula[i]) {
                case '*': {
                     stackLen++;
                     options[stackLen] = (n * m);
                     break;
                }
                case '/': {
                     stackLen++;
                     options[stackLen] = (n / m);
                     break;
                }
                case '+': {
                     stackLen++;
                     options[stackLen] = (n + m);
                     break;
                }
                case '-': {
                     stackLen++;
                     options[stackLen] = (n - m);
                     break;
                }
            }
        }
    }

    printf("
結果為: %.2f
" , options[0]);
}

執(zhí)行結果

# ./a.out
3298+*3/35/*+

結果為: 9.80
#

審核編輯：劉清