資料結構實戰：中綴表達式轉後綴表達式（堆疊應用）

演算法原理

中綴表達式（如 1+(2*3)）不便於電腦直接計算，需轉為後綴表達式（1 2 3 * +），再利用堆疊求值。

轉換規則

1. 掃描中綴表達式，遇運算數直接輸出。
2. 遇運算符，若堆疊頂優先級 >= 當前運算符，彈出堆疊頂輸出，直到優先級 < 當前或堆疊空，再將當前運算符入堆疊。
3. 遇左括號直接入堆疊；遇右括號彈出輸出直到遇左括號（左括號僅彈出不輸出）。
4. 掃描結束，將堆疊剩餘運算符依序彈出輸出。

C 語言實現（7 運算符版：+ - * / ^ ( )）

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#define MAX 511

char mid[MAX], post[MAX];
int stack_op[MAX], top_op = -1;
int stack_val[MAX], top_val = -1;

int priority(char c) {
    switch (c) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        case '^': return 3;
        case '(': return 0;
        default: return -1;
    }
}

void infix_to_postfix() {
    int i, j = 0;
    for (i = 0; mid[i]; i++) {
        if (isdigit(mid[i])) {
            post[j++] = mid[i];
            post[j++] = ' '; // 分隔多位數
        } else if (mid[i] == '(') {
            stack_op[++top_op] = '(';
        } else if (mid[i] == ')') {
            while (top_op >= 0 && stack_op[top_op] != '(')
                post[j++] = stack_op[top_op--], post[j++] = ' ';
            top_op--; // 彈出 '('
        } else {
            while (top_op >= 0 && priority(stack_op[top_op]) >= priority(mid[i]))
                post[j++] = stack_op[top_op--], post[j++] = ' ';
            stack_op[++top_op] = mid[i];
        }
    }
    while (top_op >= 0)
        post[j++] = stack_op[top_op--], post[j++] = ' ';
    post[j] = '\0';
}

int eval_postfix() {
    int i = 0, num = 0;
    while (post[i]) {
        if (isdigit(post[i])) {
            num = 0;
            while (isdigit(post[i]))
                num = num * 10 + (post[i++] - '0');
            stack_val[++top_val] = num;
        } else if (post[i] != ' ') {
            int b = stack_val[top_val--];
            int a = stack_val[top_val--];
            switch (post[i]) {
                case '+': stack_val[++top_val] = a + b; break;
                case '-': stack_val[++top_val] = a - b; break;
                case '*': stack_val[++top_val] = a * b; break;
                case '/': stack_val[++top_val] = a / b; break;
                case '^': stack_val[++top_val] = (int)pow(a, b); break;
            }
            i++;
        } else i++;
    }
    return stack_val[top_val];
}

int main() {
    printf("輸入中綴表達式: ");
    scanf("%s", mid);
    infix_to_postfix();
    printf("後綴表達式: %s\n", post);
    printf("計算結果: %d\n", eval_postfix());
    return 0;
}

關鍵點

• 多位數處理：輸出時以空格分隔。
• 乘方運算 ^ 優先級最高，右結合。
• 堆疊分離：運算符堆疊與運算數堆疊分開管理。