C++ 棧應用經典：括號匹配算法完整實現與講解

C++ 棧應用經典：括號匹配算法完整實現

問題描述

給定一個僅包含 ( ) [ ] 的字符串，判斷括號是否正確匹配。匹配規則：左括號入棧，遇右括號出棧並比對類型；最終棧為空且過程無類型不匹配，則匹配成功。

算法流程

1. 初始化空棧。
2. 遍歷字符串每字符 ch：
    • ch == '(' || '[' → 入棧。
    • ch == ')' → 若棧空或棧頂 ≠ '('，報錯「) 不匹配」；否則出棧。
    • ch == ']' → 同理比對 '['。
   
3. 遍歷結束：若棧非空 →「數量不匹配」；否則 →「匹配」。

完整代碼（C++，含手寫棧結構）

#include <iostream>
using namespace std;
#define MAX 100

struct Stack {
    int top;
    int maxSize;
    char *element;
};

void init(Stack *s, int n) {
    s->top = -1;
    s->maxSize = n;
    s->element = new char[n];
}
bool isEmpty(Stack *s) { return s->top == -1; }
bool isFull(Stack *s) { return s->top == s->maxSize - 1; }
void push(Stack *s, char x) {
    if (!isFull(s)) s->element[++s->top] = x;
    else cout << "棧滿" << endl;
}
char pop(Stack *s) {
    if (!isEmpty(s)) return s->element[s->top--];
    else { cout << "棧空" << endl; return -1; }
}

int main() {
    Stack *s = new Stack;
    init(s, MAX);
    bool ok = true, ok1 = true, ok2 = true;
    cout << "請輸入字符串:" << endl;
    char ch;
    while ((ch = getchar()) != '\n') {
        switch (ch) {
            case '(': case '[': push(s, ch); break;
            case ')':
                if (pop(s) != '(' && ok2) { cout << "')' 不匹配" << endl; ok1 = ok = false; }
                break;
            case ']':
                if (pop(s) != '[' && ok1) { cout << "']' 符號不匹配" << endl; ok2 = ok = false; }
                break;
        }
    }
    if (!isEmpty(s) && ok) cout << "數量不匹配" << endl;
    else if (ok) cout << "匹配" << endl;
    system("pause");
    return 0;
}

關鍵點總結

• 棧的後進先出（LIFO）特性天然契合括號嵌套結構。
• 需區分「類型不匹配」（如 (]）與「數量不匹配」（如 ((）。
• 實際工程中建議直接使用 std::stack<char>，代碼更簡潔安全。

擴展：同樣邏輯可處理 { }、HTML 標籤匹配、編譯器語法分析等場景。