中綴轉後綴表達式：經典棧應用解析（含完整 C 實現）

問題描述

給定一個中綴表達式（運算元為個位數，運算符僅含 + - * / 及括號），請將其轉換為後綴表達式（逆波蘭表示法）。測試資料組數 T < 10，每行表達式長度 ≤ 1000，保證合法且無負數。

演算法思路：運算元輸出、運算符入棧

1. 掃描中綴表達式每一字元：
2. 若為數字（0-9），直接輸出至後綴串；
3. 若為左括號 (，直接壓入運算符棧；
4. 若為右括號 )，彈出棧頂運算符並輸出，直到遇到左括號（左括號僅彈出不輸出）；
5. 若為運算符 + - * /：
   • 若棧頂運算符優先級 ≥ 當前運算符，則彈出棧頂輸出，重複直到條件不滿足；
   • 將當前運算符壓入棧。
6. 掃描結束後，將棧中剩餘運算符依序彈出輸出。

優先級規則

• * / 優先級高於 + -
• 同優先級左結合
• 括號內優先級最高

完整 C 程式碼（含註釋）

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

#define MAX_LEN 1000

int main(void) {
    int T;
    scanf("%d", &T);
    while (T--) {
        char infix[MAX_LEN + 1];
        scanf("%s", infix);

        char opStack[MAX_LEN];
        int top = -1;                 // 運算符棧頂指標
        char postfix[MAX_LEN * 2];    // 後綴結果緩衝
        int pIdx = 0;                 // 後綴串索引

        for (int i = 0; infix[i]; ++i) {
            char ch = infix[i];
            if (ch >= '0' && ch <= '9') {
                postfix[pIdx++] = ch;                 // 運算元直接輸出
            } else if (ch == '(') {
                opStack[++top] = ch;                  // 左括號入棧
            } else if (ch == ')') {
                while (top >= 0 && opStack[top] != '(') {
                    postfix[pIdx++] = opStack[top--]; // 彈出至左括號
                }
                if (top >= 0) --top;                  // 丟棄左括號
            } else { // 運算符 + - * /
                while (top >= 0 && opStack[top] != '(') {
                    char topOp = opStack[top];
                    // 若棧頂優先級 >= 當前，則彈出
                    if ((topOp == '*' || topOp == '/') ||
                        (ch == '+' || ch == '-')) {
                        postfix[pIdx++] = opStack[top--];
                    } else break;
                }
                opStack[++top] = ch;                  // 當前運算符入棧
            }
        }
        while (top >= 0) {                            // 清空剩餘運算符
            postfix[pIdx++] = opStack[top--];
        }
        postfix[pIdx] = '\0';
        puts(postfix);
    }
    return 0;
}

範例驗證

複雜度分析

• 時間複雜度：O(n)，n 為表達式長度，每字元進出棧各一次。
• 空間複雜度：O(n)，運算符棧與輸出緩衝。

常見錯誤提醒

• 忘記處理多位數運算元（本題限定個位數，故無需處理）。
• 右括號處理時未檢查棧是否為空（題目保證合法，可省略）。
• 運算符優先級判斷邏輯錯誤，建議封裝 precedence(char op) 函式提高可讀性。

延伸應用

後綴表達式便於機器求值，只需一個運算元棧即可完成計算，是編譯器、解析器的核心基礎。