中綴轉後綴表達式：棧的經典應用（C語言實現）

中綴轉後綴表達式：棧的經典應用（C語言實現）

問題背景：中綴表達式（如 a+b*(c+d)）符合人類閱讀習慣，但計算機難以直接求值。後綴表達式（逆波蘭式，如 abcd+*+）無需括號，掃描一次即可用棧計算。本題要求將只包含個位數運算元、運算符 + - * / 及括號的中綴表達式轉為後綴形式。

算法核心（Dijkstra Shunting-yard 算法簡化版）

1. 掃描輸入字符：
• 若為數字，直接輸出。
• 若為 (，入棧。
• 若為 )，彈出棧頂運算符輸出，直到遇到 (（丟棄括號）。
• 若為運算符 + -：彈出棧中優先級 ≥ 當前運算符的運算符輸出，然後入棧。
• 若為運算符 * /：僅彈出棧中 * / 輸出，然後入棧（因同級左結合）。
2. 掃描結束後，將棧中剩餘運算符依次輸出。

完整代碼

#include <stdio.h>
#include <string.h>
#define MAX 1000

int main(void) {
    int n; scanf("%d", &n);
    while (n--) {
        char str[MAX], opStack[MAX], output[MAX];
        int top = -1, outLen = 0;
        scanf("%s", str);
        for (int i = 0; str[i]; ++i) {
            char ch = str[i];
            if (ch >= '0' && ch <= '9') {
                output[outLen++] = ch;
            } else if (ch == '(') {
                opStack[++top] = ch;
            } else if (ch == ')') {
                while (top >= 0 && opStack[top] != '(')
                    output[outLen++] = opStack[top--];
                top--; // 丟棄 '('
            } else if (ch == '+' || ch == '-') {
                while (top >= 0 && opStack[top] != '(')
                    output[outLen++] = opStack[top--];
                opStack[++top] = ch;
            } else { // * /
                while (top >= 0 && (opStack[top] == '*' || opStack[top] == '/'))
                    output[outLen++] = opStack[top--];
                opStack[++top] = ch;
            }
        }
        while (top >= 0) output[outLen++] = opStack[top--];
        output[outLen] = '\0';
        puts(output);
    }
    return 0;
}

樣例測試

輸入：
2
1+2
(1+2)*3+4*5

輸出：
12+
12+3*45*+

程序正確處理了運算符優先級、左結合性及括號嵌套，是編譯原理與數據結構教學中的標準案例。