Java 中的括号匹配算法详解

1. 概述

括号匹配（Balanced Brackets），也常被称为括号平衡问题，是编程中非常经典的一道算法题。这类问题在编译器解析、表达式求值、JSON 校验等场景中都有广泛应用。

本文将深入讲解如何判断一个字符串中的括号是否完全匹配，并提供两种实现方案。这类字符串在形式语言理论中属于 Dyck 语言 的范畴，感兴趣的同学可以自行查阅维基百科了解背景。

2. 问题定义

我们定义的“括号”包括以下六种字符：
(, ), [, ], {, }

一组括号被认为是匹配的，当且仅当：

✅ 开括号 (、[、{ 出现在对应的闭括号 )、]、} 左侧
✅ 所有括号必须正确嵌套，不能交叉
❌ 字符串中不能包含任何非括号字符（如字母、数字、特殊符号等）

⚠️ 特殊情况说明：

null 输入视为 不合法（返回 false）
空字符串 "" 视为合法（返回 true）

✅ 合法示例

()
[()]
{[()]}
([{{[(())]}}])

❌ 非法示例

abc[](){}         // 包含非括号字符
{{[]()}}}}        // 多余的 }
{[(])}            // 交叉嵌套，不合法

踩坑提醒：很多人忽略“不能包含非括号字符”这一条，导致测试用例失败。

3. 解法概览

解决括号匹配问题主要有两种思路：

字符串替换法：循环删除成对的括号，直到无法删除
双端队列（Deque）法：利用栈结构进行匹配，效率更高

下面我们逐一实现。

4. 基础校验

首先定义方法签名：

public boolean isBalanced(String str)

在正式处理前，先做几项快速校验：

if (str == null || str.length() % 2 != 0) {
    return false;
}
char[] ch = str.toCharArray();
for (char c : ch) {
    if (!(c == '{' || c == '[' || c == '(' || c == '}' || c == ']' || c == ')')) {
        return false;
    }
}

校验逻辑说明：

null 直接返回 false
长度为奇数 ⇒ 必有括号无法配对 ⇒ 返回 false
只要出现非括号字符 ⇒ 立即返回 false

通过校验后，我们再进入核心匹配逻辑。

5. 使用 String.replaceAll 方法

该方法思路简单粗暴：不断删除成对的括号，直到删无可删。

while (str.contains("()") || str.contains("[]") || str.contains("{}")) {
    str = str.replaceAll("\\(\\)", "")
             .replaceAll("\\[\\]", "")
             .replaceAll("\\{\\}", "");
}
return str.length() == 0;

优缺点分析

✅ 优点：

代码简洁，逻辑清晰，容易理解

❌ 缺点：

replaceAll 是正则操作，性能较差
每次替换都会生成新字符串，内存开销大
时间复杂度不稳定，最坏可达 O(n²)

适合小数据量或教学演示，生产环境不推荐。

6. 使用 Deque 实现栈结构

这才是工业级写法。我们使用 Deque 模拟栈（LIFO），逐字符扫描，遇到开括号入栈，闭括号尝试匹配出栈。

核心实现

Deque<Character> deque = new LinkedList<>();
for (char ch : str.toCharArray()) {
    if (ch == '{' || ch == '[' || ch == '(') {
        deque.addFirst(ch);
    } else {
        if (!deque.isEmpty()
            && ((deque.peekFirst() == '{' && ch == '}')
             || (deque.peekFirst() == '[' && ch == ']')
             || (deque.peekFirst() == '(' && ch == ')'))) {
            deque.removeFirst();
        } else {
            return false;
        }
    }
}
return deque.isEmpty();

关键点说明

使用 LinkedList 实现 Deque 接口，支持高效的头插头删
addFirst() 相当于入栈，removeFirst() 相当于出栈
匹配失败或栈空时遇到闭括号 ⇒ 直接返回 false
最终栈必须为空，表示所有括号都已匹配

时间复杂度

✅ 时间复杂度：O(n)
✅ 空间复杂度：O(n)

推荐在实际项目中使用此方案，稳定高效。

7. 总结

本文详细解析了括号匹配问题的两种实现方式：

方法	适用场景	建议
`String.replaceAll`	学习理解	❌ 不推荐生产使用
`Deque` 栈结构	实际项目	✅ 强烈推荐

两种方法都通过了基础校验和边界测试，代码健壮性良好。

完整代码已托管至 GitHub：
https://github.com/baomidou/tutorials/tree/master/algorithms/brackets

Persistence

REST

Security