堆疊經典演算法全解析：括號匹配、後綴運算與中綴轉換

編輯：關於C語言

引言

堆疊（Stack）作為「後進先出」（LIFO）的核心資料結構，是解決許多經典計算機科學問題的利器。本文系統梳理三大堆疊經典應用——括號匹配、後綴表達式求值、中綴轉後綴表達式——並附上完整 C 語言實作碼，助你徹底掌握堆疊演算法精髓。

一、括號匹配演算法

演算法邏輯

建立空堆疊，逐字元讀入輸入字串。
遇到左括號 ( [ { → 入堆疊。
遇到右括號 ) ] } →
- 若堆疊為空 → 匹配失敗（多餘右括號）。
- 彈出堆疊頂元素，若類型不匹配（如 ( 對 ]）→ 匹配失敗。
輸入結束後，若堆疊非空 → 匹配失敗（缺少右括號）；否則 匹配成功。

代碼關鍵點

int match(char *cs, int size) {
    Stack s = CreateStack(size);
    for (int i = 0; i < size; i++) {
        char ch = cs[i];
        if (left(ch)) Push(ch, s);
        else if (right(ch))
            if (IsEmpty(s) || !pair(TopAndPop(s), ch)) return FALSE;
    }
    return IsEmpty(s) ? TRUE : FALSE;
}

輔助函式 left()、right()、pair() 封裝了判斷邏輯，使主流程清晰易讀。

二、後綴表達式求值

演算法邏輯

假設輸入為合法後綴表達式（逆波蘭表示法），運算元為個位數字：

建立空堆疊，逐字元掃描。
若為數字（isdigit()）→ 轉為整數 入堆疊。
若為運算元 + - * / → 彈出兩個運算元（注意順序：第二個彈出的是左運算元），計算結果 入堆疊。
掃描結束，堆疊頂唯一元素即為最終結果。

代碼亮點

case '-':
    tmp = TopAndPop(s);          // 右運算元
    Push(tmp - TopAndPop(s), s); // 左運算元 - 右運算元
    break;
case '/':
    tmp = TopAndPop(s);
    Push(tmp / TopAndPop(s), s); // 左運算元 / 右運算元
    break;

減法與除法順序敏感，必須用暫存變數保證正確順序，這是初學者常犯錯誤的地方。

三、中綴轉後綴表達式

演算法邏輯

建立空堆疊（存放運算元），逐字元掃描中綴表達式。
運算元（字母/數字） → 直接輸出。
運算元 + - * / →
- 若堆疊不空且堆疊頂運算元優先級 大於等於 當前運算元 → 彈出並輸出堆疊頂運算元（重複直到條件不滿足）。
- 將當前運算元 入堆疊。
左括號 ( → 直接 入堆疊（優先級最低，作為邊界）。
右括號 ) → 彈出並輸出堆疊元素，直到遇到 ( 為止（( 僅彈出不輸出）。
掃描結束，將堆疊剩餘運算元依序彈出輸出。

優先級比較函式

static int compareSymbol(char symbol, char prevSymbol) {
    if (prevSymbol == '(') return 1; // 當前優先級高於 '('
    if (symbol == '+' || symbol == '-') {
        return (prevSymbol == '+' || prevSymbol == '-') ? 0 : -1;
    } else { // * /
        return (prevSymbol == '+' || prevSymbol == '-') ? 1 : 0;
    }
}

返回值約定：1 當前優先級較高，0 相等，-1 較低。此設計巧妙處理了括號與同優先級運算元的左結合性。

完整測試主程式

int main() {
    // 1. 括號匹配測試
    char chars[] = "1 + {5 * [4 - (4 - 10) + 2 * 23] + 12 / 11}(";
    puts(match(chars, strlen(chars)) ? "true" : "false"); // false (多一個 '(')

    // 2. 後綴求值測試: 6 5 2 3 + 8 * + 3 + *  => 6 * (5 + (2+3)*8 + 3) = 6 * (5+40+3) = 288
    char exp1[] = "6523+8*+3+*";
    printf("postfixValue=%d\n", postfixValue(exp1, strlen(exp1))); // 288

    // 3. 中綴轉後綴測試: a+b*c+(d*e+f)*g => a b c * + d e * f + g * +
    char exp2[] = "a+b*c+(d*e+f)*g";
    convertExpression(exp2, strlen(exp2)); // 輸出: a b c * + d e * f + g * +
    return 0;
}