括號匹配問題：堆棧法解題詳解與常見錯誤避坑指南

題目描述

輸入 N（0 < N ≤ 100）組測試數據，每組為一個長度 < 10000 的非空字符串 S，僅包含 '['、']'、'('、')' 四種字符。判斷括號是否完全匹配，匹配輸出 yes，否則輸出 no。

核心算法：堆棧（或模擬堆棧）

括號匹配的經典解法是使用堆棧：

• 遇到左括號 '(' 或 '['，入棧。
• 遇到右括號 ')' 或 ']'，檢查棧頂是否為對應左括號：匹配則出棧，不匹配則直接判定失敗。
• 遍歷結束後，棧為空則完全匹配，否則有剩餘左括號未閉合。

原代碼邏輯分析與潛在缺陷

原代碼嘗試用數組 num[i] 模擬堆棧，變量 a 作為棧頂索引，b 標記是否出現「無左括號可匹配的右括號」。邏輯大體正確，但存在以下隱患：

1. 數組越界風險：num[i][a-1] 在 a==0 時訪問 num[i][-1]，屬於未定義行為。雖然代碼有 if(a==0) b=0 判斷，但緊隨其後的 if(num[i][a-1]=='(') 仍會執行，需用 else if 或大括號隔離。
2. 測試用例數組尺寸固定：char num[n][10000] 作為 VLA（變長數組），棧上分配可能導致棧溢出（100×10000 = 1MB），建議動態分配或逐行處理。
3. 輸入處理：scanf("%s", num[i]) 遇到空白字符停止，若測試數據包含空行或前導空格可能讀取異常，建議用 fgets 並去除換行符。
4. 邏輯簡化空間：b 標記可合併進匹配失敗的直接返回，無需遍歷完畢再判斷。

優化後的標準實現（C語言）

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

#define MAX_LEN 10000

int is_matched(const char *s) {
    char *stack = malloc(strlen(s) + 1); // 動態分配堆棧，足夠大
    if (!stack) return 0;
    int top = -1;

    for (int i = 0; s[i]; i++) {
        switch (s[i]) {
            case '(':
            case '[':
                stack[++top] = s[i];
                break;
            case ')':
                if (top < 0 || stack[top] != '(') { free(stack); return 0; }
                top--;
                break;
            case ']':
                if (top < 0 || stack[top] != '[') { free(stack); return 0; }
                top--;
                break;
        }
    }
    int ok = (top == -1);
    free(stack);
    return ok;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    getchar(); // 吞掉換行符

    char line[MAX_LEN + 2];
    for (int i = 0; i < n; i++) {
        if (!fgets(line, sizeof(line), stdin)) break;
        line[strcspn(line, "\n")] = '\0'; // 去除換行
        printf("%s\n", is_matched(line) ? "yes" : "no");
    }
    return 0;
}

關鍵改進點

• 動態分配堆棧：避免大數組佔用棧空間，按需分配並釋放。
• 早期退出：發現不匹配立即返回 0，無需繼續遍歷。
• 安全輸入：用 fgets 讀整行，配合 strcspn 去除換行，兼容空行與前導空格。
• 代碼簡潔：switch 合並同類情況，邏輯清晰易維護。

常見測試用例

總結

括號匹配是堆棧應用的教科書級例題。原代碼思路正確但在邊界處理、內存安全、輸入健壯性上有提升空間。掌握動態堆棧 + 早期退出 + 安全輸入的標準模式，不僅能 AC 此題，更能應對各種變體（如多類型括號、帶轉義字符、流式處理等）。