第28章：字符串的括号匹配：栈的应用（'()'、'[]'、'{}'）

各位同学，今天我们来聊一个非常经典的问题——括号匹配。说白了，就是检查一段字符串里的左括号和右括号是不是成对出现的，而且顺序要对。

你可能会想：“这有什么难的？数个数不就行了？”嗯，我当年刚学编程时也是这么想的。直到有一次，我在一个配置文件解析器里遇到了嵌套的括号……那叫一个惨。数个数只能判断数量是否相等，但完全管不了顺序。比如 ([)] 这种，数量是对的，但顺序是错的。真正的括号匹配，必须用栈。

为什么是栈？

栈是一种“后进先出”的数据结构。你想想看，括号的嵌套规则是什么？最后一个出现的左括号，必须最先被匹配掉。这不就是栈的特性吗？

举个例子：{ [ ( ) ] }

• 遇到 {，入栈
• 遇到 [，入栈
• 遇到 (，入栈
• 遇到 )，检查栈顶是不是 (，是则出栈
• 遇到 ]，检查栈顶是不是 [，是则出栈
• 遇到 }，检查栈顶是不是 {，是则出栈

最后栈为空，说明匹配成功。如果中间发现栈顶不匹配，或者遍历完了栈还不为空，那就是匹配失败。

代码实现

我直接上代码。这是我最常用的一个版本，简洁且健壮。

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

#define MAX_LEN 1000

// 栈结构
typedef struct {
    char data[MAX_LEN];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

bool push(Stack *s, char c) {
    if (s->top >= MAX_LEN - 1) return false;
    s->data[++s->top] = c;
    return true;
}

char pop(Stack *s) {
    if (s->top == -1) return '\0';
    return s->data[s->top--];
}

char peek(Stack *s) {
    if (s->top == -1) return '\0';
    return s->data[s->top];
}

bool isMatchingPair(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

bool isValid(char *s) {
    Stack stack;
    initStack(&stack);
    
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            push(&stack, c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stack.top == -1) return false;  // 栈空，说明没有左括号匹配
            char top = pop(&stack);
            if (!isMatchingPair(top, c)) return false;  // 不匹配
        }
        // 其他字符忽略
    }
    
    return stack.top == -1;  // 栈空才合法
}

int main() {
    char test1[] = "({[]})";
    char test2[] = "([)]";
    char test3[] = "((())";
    
    printf("%s: %s\n", test1, isValid(test1) ? "合法" : "不合法");
    printf("%s: %s\n", test2, isValid(test2) ? "合法" : "不合法");
    printf("%s: %s\n", test3, isValid(test3) ? "合法" : "不合法");
    
    return 0;
}

这段代码我用了很多年。你注意看 isMatchingPair 函数，它把三种括号的匹配关系封装起来了。这样主逻辑就非常清晰：遇到左括号就压栈，遇到右括号就检查栈顶。

避坑指南

我曾经在一个生产环境里踩过一个坑。当时我写了一个表达式解析器，括号匹配的逻辑看起来没问题，但测试时总是报错。排查了半天，发现是字符串里混入了中文括号（全角符号）。'（' 和 '）' 跟 ASCII 的 '(' 和 ')' 长得像，但 ASCII 码完全不同。

所以，如果你处理的是用户输入的字符串，一定要先做字符过滤或编码检查。否则，栈里存了一个全角左括号，遇到半角右括号，匹配肯定失败。

流程图：括号匹配的核心逻辑

下面我用一张 SVG 图来展示整个流程。你跟着箭头走一遍，就能理解栈是怎么工作的了。

复杂度分析

指标	值	说明
时间复杂度	O(n)	每个字符只处理一次，入栈出栈都是 O(1)
空间复杂度	O(n)	最坏情况下，所有字符都是左括号，全部入栈

这个算法的时间复杂度是线性的，空间复杂度也是线性的。你想想看，如果字符串有 100 万个字符，最坏情况下栈里要存 100 万个左括号。所以，如果你在嵌入式系统里用这个算法，一定要考虑栈的容量限制。

扩展思考

除了括号匹配，栈还能用来做很多事情。比如表达式求值、HTML 标签匹配、函数调用栈模拟等等。我当年做一个 JSON 解析器时，就用栈来匹配花括号和方括号，原理一模一样。

另外，如果你需要支持多种括号类型，比如 <> 或者自定义的成对符号，只需要在 isMatchingPair 里加几个条件就行了。代码的扩展性很好。

好了，关于括号匹配的栈实现，我就讲到这里。记住，栈是解决这类嵌套匹配问题的最优工具。下次你遇到类似需求，别犹豫，直接上栈。