括號匹配問題：堆疊經典應用與 C++ STL 完整解法

問題描述

• 輸入 N 組測資（N ≤ 100）
• 每組一字串 S（長度 < 10000，非空），僅含 ()[]
• 判斷括號是否正確配對：類型匹配、順序正確、嵌套合法
• 輸出 Yes / No

核心邏輯：堆疊（LIFO）

1. 掃描字串每個字元
2. 左括號 ( [ → 入堆疊
3. 右括號 ) ] →
   • 堆疊空 → 不匹配
   • 堆疊頂非對應左括號 → 不匹配
   • 匹配 → 出堆疊
4. 掃描結束 → 堆疊必須為空

快速失敗優化

• 字串長度為奇數 → 直接 No
• 右括號開頭 → 直接 No

C++ STL 完整解法（AC）

#include <cstdio>
#include <stack>
#include <cstring>

using namespace std;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        char s[10050];
        scanf("%s", s);
        int n = strlen(s);
        
        /* 快速失敗 */
        if (n % 2 == 1) {
            printf("No\n");
            continue;
        }
        
        stack<char> st;
        int ok = 1;
        
        for (int i = 0; i < n && ok; i++) {
            char ch = s[i];
            if (ch == '(' || ch == '[') {
                st.push(ch);
            } else if (ch == ')') {
                if (st.empty() || st.top() != '(') ok = 0;
                else st.pop();
            } else if (ch == ']') {
                if (st.empty() || st.top() != '[') ok = 0;
                else st.pop();
            }
        }
        
        if (!st.empty()) ok = 0;
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
}

C 語言手寫堆疊版本（無 STL 環境）

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

#define MAXN 10000

char stack[MAXN];
int top;

void push(char c) { stack[top++] = c; }
char pop(void) { return stack[--top]; }
char peek(void) { return stack[top - 1]; }
int is_empty(void) { return top == 0; }

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        char s[MAXN + 5];
        scanf("%s", s);
        int n = strlen(s);
        
        if (n % 2) { puts("No"); continue; }
        
        top = 0;
        int ok = 1;
        for (int i = 0; i < n && ok; i++) {
            if (s[i] == '(' || s[i] == '[') push(s[i]);
            else if (s[i] == ')') { if (is_empty() || peek() != '(') ok = 0; else pop(); }
            else if (s[i] == ']') { if (is_empty() || peek() != '[') ok = 0; else pop(); }
        }
        if (!is_empty()) ok = 0;
        puts(ok ? "Yes" : "No");
    }
    return 0;
}

樣例驗證

輸入:
3
[(])
(])
([[]()])

輸出:
No
No
Yes

解析:
[(])  → [ ( ] )  第 3 字元 ] 對應堆疊頂 ( → 類型不符
(])   → ( ]      第 2 字元 ] 對應堆疊頂 ( → 類型不符
([[]()]) → 完美嵌套匹配

擴展：支援多種括號與錯誤位置報告

/* 通用匹配表 */
struct Pair { char open, close; };
struct Pair pairs[] = {{'(', ')'}, {'[', ']'}, {'{', '}'}, {'<', '>'}};

int is_open(char c) { for (auto p: pairs) if (p.open == c) return 1; return 0; }
char matching_open(char close) { for (auto p: pairs) if (p.close == close) return p.open; return 0; }

/* 掃描時記錄位置 */
struct Item { char ch; int pos; };
stack<Item> st;
for (int i = 0; i < n; i++) {
    if (is_open(s[i])) st.push({s[i], i});
    else {
        if (st.empty() || st.top().ch != matching_open(s[i])) {
            printf("Error at pos %d: %c\n", i, s[i]);
            ok = 0; break;
        }
        st.pop();
    }
}

複雜度分析

• 時間：O(n) —— 每字元進棧/出棧各一次
• 空間：O(n) —— 最壞全為左括號
• 單趟掃描、線性時間、最優解

常見錯誤與測資