數據結構實戰：C語言棧實現括號匹配驗證算法

編輯：關於C語言

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

利用棧後進先出特性，實現圓括號、方括號嵌套匹配驗證，包含棧完整封裝、匹配邏輯、錯誤處理。

棧封裝 (順序棧)


#define MAX_SIZE 100
#define INCREMENT 10

typedef char ElemType;
typedef struct {
    ElemType *base;
    ElemType *top;
    int size;
} SqStack;

int init(SqStack *s) {
    s->base = malloc(MAX_SIZE * sizeof(ElemType));
    if (!s->base) return 0;
    s->top = s->base;
    s->size = MAX_SIZE;
    return 1;
}

int push(SqStack *s, ElemType e) {
    if (s->top - s->base >= s->size) {
        s->base = realloc(s->base, (s->size + INCREMENT) * sizeof(ElemType));
        if (!s->base) return 0;
        s->top = s->base + s->size;
        s->size += INCREMENT;
    }
    *s->top++ = e;
    return 1;
}

int pop(SqStack *s, ElemType *e) {
    if (s->top == s->base) return 0;
    *e = *--s->top;
    return 1;
}

int isEmpty(SqStack *s) {
    return s->top == s->base;
}

括號匹配核心算法


int match(SqStack *s, char *str) {
    char ch;
    for (int i = 0; str[i]; i++) {
        switch (str[i]) {
            case '(': case '[':
                push(s, str[i]);  // 左括號入棧
                break;
            case ')':
                if (!pop(s, &ch) || ch != '(') return 0;
                break;
            case ']':
                if (!pop(s, &ch) || ch != '[') return 0;
                break;
        }
    }
    return isEmpty(s);  // 棧空為匹配成功
}

算法邏輯圖解

輸入: "([()])"
掃描: ( [ ( ) ] )
棧變化:
  push '('  -> ['(']
  push '['  -> ['(', '[']
  push '('  -> ['(', '[', '(']
  pop  '('  -> ['(', '[']   匹配 ')'
  pop  '['  -> ['(']       匹配 ']'
  pop  '('  -> []          匹配 ')'
棧空 -> 匹配成功

錯誤情況覆蓋

錯誤類型	輸入示例	檢測點
右括號多	())	pop 失敗/棧空
左括號多	((	結束時棧非空
類型不匹配	(]	pop 出 '(' != '['
嵌套錯序	[)	pop 出 '[' != '('

擴展：支援花括號與多類型


int matchAll(SqStack *s, char *str) {
    static const char *left = "([{";
    static const char *right = ")]}";
    
    for (int i = 0; str[i]; i++) {
        char *p = strchr(left, str[i]);
        if (p) push(s, str[i]);
        else if ((p = strchr(right, str[i]))) {
            char expected = left[p - right];
            char actual;
            if (!pop(s, &actual) || actual != expected) return 0;
        }
    }
    return isEmpty(s);
}