C 語言括號匹配驗證：不使用堆疊的巧妙字串原地標記法

題目背景

南陽理工 OJ 題目：給定只含 ()[] 的字串，判斷括號是否合法配對。限制：字串長度 < 10000，測試組數 < 5。標準解法用堆疊，但作者未學資料結構，另闢蹊徑。

核心演算法：原地配對消除法

利用字串可修改特性，採用雙指針回溯 + 字元標記策略：

1. 快速失敗檢查：長度為奇數、首字元為右括號 → 直接 No
2. 正向掃描：遇到右括號 ) 或 ]
3. 回溯尋找匹配左括號：從當前位置向左跳過已標記 '0' 的字元
4. 驗證配對合法性：利用 ASCII 碼差值判斷：
   • ')' - '(' = 1
   • ']' - '[' = 2
   • 其他差值 → 類型不匹配 → No
5. 標記消除：配對成功將雙方標記為 '0'
6. 最終判定：若最後一字元為 '0'（說明所有字元配對完畢）→ Yes

完整代碼實現

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

void deal(char str[]) {
    int len = strlen(str);
    int i, j, flag;
    
    // 快速失敗
    if (len % 2 != 0 || str[0] == ')' || str[0] == ']') {
        printf("No\n");
        return;
    }
    
    for (i = 0; i < len; i++) {
        if (str[i] == ')' || str[i] == ']') {
            // 向左尋找未配對的左括號
            for (j = i - 1; j >= 0; j--) {
                if (str[j] == '0') continue; // 跳過已配對
                
                int diff = str[i] - str[j];
                if (diff != 1 && diff != 2) { // 類型不匹配
                    printf("No\n");
                    return;
                }
                // 配對成功，標記消除
                str[i] = str[j] = '0';
                break;
            }
        }
    }
    
    // 全部配對完成的標誌：最後一字元被標記
    if (str[len - 1] == '0')
        printf("Yes\n");
    else
        printf("No\n"); // 有殘留未配對左括號
}

int main() {
    int n;
    char str[10000];
    scanf("%d", &n);
    while (n--) {
        scanf("%s", str);
        deal(str);
    }
    return 0;
}

演算法分析

優缺點總結

優點：無需堆疊資料結構，思路直觀，代碼極短，適合受限環境（如嵌入式無標準庫）。
缺點：破壞原始字串、O(n²) 效率低、擴展性差（新增括號類型需修改差值判斷邏輯）、無法輸出錯誤位置。

進階思考：為何堆疊是標準解？

堆疊天然契合「後進先出」的括號嵌套語義：

// 堆疊版核心邏輯 (O(n) 時間, O(n) 空間)
for (c : str) {
    if (c == '(' || c == '[') push(c);
    else if (c == ')' && top() == '(') pop();
    else if (c == ']' && top() == '[') pop();
    else return false;
}
return empty();

堆疊法可線性掃描、支援任意括號類型、易於擴展錯誤報告，是工業級解法。本文方法屬於「特定約束下的技巧性解法」，理解其局限性同樣重要。