括号匹配算法题的核心是判断字符串中的各类括号是否按照规则正确配对，常见的括号类型包括小括号、中括号和大括号。实现该算法的关键是利用栈的先进后出特性，逐字符处理字符串并校验配对情况。
算法实现思路
整个算法的处理流程可以分为以下几个步骤：
- 首先创建一个空栈，用来存储遍历过程中遇到的左括号
- 创建一个映射关系，记录右括号对应的左括号，方便后续配对校验
- 遍历字符串的每一个字符，判断当前字符的类型
- 如果是左括号，直接压入栈中
- 如果是右括号，先判断栈是否为空，为空则说明没有对应的左括号，直接返回不匹配；不为空则弹出栈顶元素，对比是否是当前右括号对应的左括号，不匹配则返回失败
- 遍历结束后，判断栈是否为空，为空说明所有左括号都完成了配对，返回匹配成功，否则返回失败
PHP代码实现
下面是完整的PHP实现代码，包含边界情况的处理：
<?php
/**
* 判断字符串括号是否匹配
* @param string $str 待检测的字符串
* @return bool 匹配返回true，否则返回false
*/
function isBracketMatch($str) {
// 定义右括号和左括号的映射关系
$matchMap = [
')' => '(',
']' => '[',
'}' => '{'
];
// 左括号集合，用于快速判断字符是否为左括号
$leftBrackets = ['(', '[', '{'];
// 初始化栈
$stack = [];
// 遍历字符串的每个字符
$len = strlen($str);
for ($i = 0; $i < $len; $i++) {
$char = $str[$i];
// 当前字符是左括号，压入栈
if (in_array($char, $leftBrackets)) {
array_push($stack, $char);
}
// 当前字符是右括号
elseif (isset($matchMap[$char])) {
// 栈为空，没有对应的左括号，直接返回false
if (empty($stack)) {
return false;
}
// 弹出栈顶元素
$top = array_pop($stack);
// 配对不匹配，返回false
if ($top != $matchMap[$char]) {
return false;
}
}
// 非括号字符，跳过处理
}
// 遍历结束后栈为空说明所有括号都匹配
return empty($stack);
}
// 测试用例
$testCases = [
"()",
"()[]{}",
"(]",
"([)]",
"{[]}",
"",
"((("
];
foreach ($testCases as $case) {
$result = isBracketMatch($case) ? "匹配" : "不匹配";
echo "字符串: {$case}，结果: {$result}" . PHP_EOL;
}
?>
代码说明
上述代码中，isBracketMatch函数是核心实现：
$matchMap数组存储了右括号到左括号的映射，避免了多个条件判断- 使用
$leftBrackets数组存储所有左括号，方便快速判断当前字符是否为左括号 - PHP中可以用数组模拟栈的操作，
array_push实现入栈，array_pop实现出栈 - 遍历过程中遇到非括号字符直接跳过，不影响匹配结果
常见边界情况
在解题时需要注意以下几种边界场景：
- 空字符串：按照算法逻辑，空字符串遍历后栈为空，返回匹配成功
- 只有左括号：遍历结束后栈不为空，返回不匹配
- 只有右括号：遇到第一个右括号时栈为空，直接返回不匹配
- 括号交叉：比如
([)]，这种场景下虽然左右括号数量一致，但顺序不符合规则，算法会正确识别为不匹配
算法复杂度分析
该算法的时间复杂度是O(n)，只需要遍历一次字符串，n是字符串的长度。空间复杂度是O(n)，最坏情况下所有字符都是左括号，栈会存储n个元素。