字符串的括号匹配：检查括号是否匹配，生成有效的括号组合

括号匹配这个问题，说实话，是很多人在学栈结构时的第一个实战题。我记得自己刚入行那会儿，面试时就被问过「写一个括号匹配检查器」。当时我心想，这还不简单？结果写出来的代码漏洞百出——单引号、双引号、花括号混在一起，直接崩了。

今天咱们就把这个知识点彻底讲透。你想想看，括号匹配其实就两个核心问题：检查已有的字符串是否合法，以及生成所有可能的合法括号组合。这两件事，一个靠栈，一个靠回溯。

一、括号匹配的核心逻辑

说白了，括号匹配就是「后开先闭」的规则。你打开一个左括号，必须有一个对应的右括号在后面等着。而且顺序不能乱——( [ ] ) 是合法的，( [ ) ] 就不行。

为什么用栈？因为栈是天然的「后进先出」结构。遇到左括号就压栈，遇到右括号就弹栈检查。如果栈顶的左括号和当前右括号不匹配，那字符串就是非法的。

二、检查括号是否匹配

先看一个最简单的实现。我习惯用数组模拟栈，因为 C 语言里数组操作更直观，而且性能也好。

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

int isValid(char *s) {
    int len = strlen(s);
    char stack[len];
    int top = -1;

    for (int i = 0; i < len; i++) {
        char c = s[i];
        // 左括号入栈
        if (c == '(' || c == '[' || c == '{') {
            stack[++top] = c;
        }
        // 右括号匹配
        else if (c == ')' || c == ']' || c == '}') {
            if (top == -1) return 0;  // 栈空，无左括号匹配
            char left = stack[top--];
            // 检查是否匹配
            if ((c == ')' && left != '(') ||
                (c == ']' && left != '[') ||
                (c == '}' && left != '{')) {
                return 0;
            }
        }
        // 其他字符忽略（比如字母、数字）
    }
    return top == -1;  // 栈空才合法
}

int main() {
    char test1[] = "()[]{}";
    char test2[] = "([)]";
    printf("%d\n", isValid(test1));  // 输出 1
    printf("%d\n", isValid(test2));  // 输出 0
    return 0;
}

这段代码逻辑很清晰。但我曾经在项目里踩过一个坑——忽略了字符串中的普通字符。比如 a(b)c 这种，如果没做过滤，直接报非法。所以上面代码里，我特意把非括号字符跳过了。

三、生成有效的括号组合

检查匹配是第一步。更难的是「生成所有合法的括号组合」。比如给你 n=3，你要输出 ((()))、(()())、(())()、()(())、()()() 这五种。

怎么做？回溯法。说白了就是「试错」——每一步你可以选择放左括号或者右括号，但必须保证当前字符串始终是合法的前缀。

什么叫合法前缀？就是任何时候，右括号的数量不能超过左括号的数量。比如 ()) 这个前缀，右括号已经比左括号多了，后面再怎么补都是非法的。

来看代码实现：

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

void backtrack(char *current, int left, int right, int n) {
    if (left == n && right == n) {
        printf("%s\n", current);
        return;
    }

    // 尝试放左括号
    if (left < n) {
        current[left + right] = '(';
        backtrack(current, left + 1, right, n);
    }

    // 尝试放右括号
    if (right < left) {
        current[left + right] = ')';
        backtrack(current, left, right + 1, n);
    }
}

void generateParenthesis(int n) {
    char *current = (char *)malloc(sizeof(char) * (2 * n + 1));
    current[2 * n] = '\0';
    backtrack(current, 0, 0, n);
    free(current);
}

int main() {
    generateParenthesis(3);
    return 0;
}

这段代码里，current[left + right] 这个写法我特别喜欢。它用 left+right 作为当前写入位置，省去了额外维护一个索引变量。嗯，小技巧，但很实用。

四、两种问题的关系

你可能会问：检查匹配和生成组合，这两件事有关系吗？

当然有。生成组合时，我们其实就是在「动态地检查匹配」。每一步放括号时，都要保证当前前缀是合法的。而检查合法性的规则，和前面栈的规则完全一致——只是这里我们不需要显式用栈，因为 left 和 right 两个计数器已经隐含了栈的信息。

我画了一张图，帮你理清这两个问题的关系：

五、避坑指南

我这些年写括号匹配代码，踩过不少坑。挑几个典型的说说：

• 栈溢出：如果字符串特别长（比如几万个字符），用固定数组模拟栈可能会溢出。我建议用动态分配，或者至少检查 top 是否超过栈容量。
• 字符编码问题：C 语言里 char 默认是 signed，如果遇到扩展 ASCII 字符，比较时可能出问题。最好用 unsigned char 或者直接比较整数值。
• 多括号类型混合：( [ ) ] 这种是经典的非法情况。很多人只检查了数量，没检查类型，结果漏判了。
• 生成组合时的递归深度：n=10 时，递归深度是 20 层，没问题。但 n=100 时，递归深度 200 层，栈空间可能不够。这时候可以考虑用迭代法。

六、总结

括号匹配这个问题，看似简单，其实包含了栈、回溯、递归、剪枝等多个知识点。我个人觉得，它是学习数据结构和算法的绝佳入门题。

检查匹配时，记住「左括号入栈，右括号匹配栈顶」这十个字就够了。生成组合时，记住「左括号数量不超过 n，右括号数量不超过左括号数量」这个约束条件。

嗯，今天就讲到这里。代码不多，但背后的思想值得反复琢磨。你可以在自己的编译器上跑一跑，试试 n=4 时能生成多少种组合——答案是 14 种。如果跑出来不对，回头看看剪枝条件是不是写错了。

---

公众号:蓝海资料掘金营，微信deep3321