修复括号匹配算法中的逻辑漏洞：为什么 "[}]" 被错误判定为合法？-java教程-PHP中文网

本文深入剖析经典括号匹配问题中一个典型逻辑缺陷——当遇到不匹配的右括号（如 ']'、'}'、)）却未及时返回 false，导致栈未清空时仍误判为有效。通过修正条件分支与添加兜底校验，确保算法严格遵循“成对、嵌套、顺序”三原则。

本文深入剖析经典括号匹配问题中一个典型逻辑缺陷——当遇到不匹配的右括号（如 `']'`、`'}'`、`)`）却未及时返回 `false`，导致栈未清空时仍误判为有效。通过修正条件分支与添加兜底校验，确保算法严格遵循“成对、嵌套、顺序”三原则。

在实现括号有效性验证（LeetCode 20）时，一个常见但隐蔽的 Bug 是：仅在栈非空且括号匹配时执行 pop()，却对“栈为空却遇到右括号”或“栈顶不匹配右括号”的情况完全忽略——这会导致非法输入（如 "[}]"）被错误接受。

以题目中失败用例 "[}]" 为例，原代码执行流程如下：

'[' → 入栈 → st = ['[']
'}' → 进入 else if(!st.isEmpty() && s.charAt(i)=='}') 分支
→ 检查 st.peek() == '{'？否（实际是 '['）→ 不执行任何操作，也不返回 false，直接跳过
']' → 同理，st.peek() == '[' 成立 → 弹出 '[' → st = []
循环结束，st.isEmpty() 为 true → 返回 true ❌（正确应为 false）

根本原因在于：所有 else if 分支均假设“右括号出现时栈必然有可匹配项”，而未处理“不匹配”或“栈空却遇右括号”的异常路径。

✅ 正确做法是：对每个右括号，必须显式校验匹配性；一旦不匹配，立即返回 false。以下是修复后的完整实现：

public boolean isValid(String s) {
    Stack<character> stack = new Stack();

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } 
        // 关键修复：对每个右括号，必须确保栈非空且栈顶匹配，否则直接失败
        else if (c == ')') {
            if (stack.isEmpty() || stack.pop() != '(') return false;
        } 
        else if (c == '}') {
            if (stack.isEmpty() || stack.pop() != '{') return false;
        } 
        else if (c == ']') {
            if (stack.isEmpty() || stack.pop() != '[') return false;
        }
        // 可选：若字符串含非法字符（如字母、数字），此处可加 default 分支抛异常或返回 false
    }

    return stack.isEmpty(); // 最终栈必须为空才合法
}</character>

? 关键改进点总结：

原子化校验：每个右括号分支内，stack.pop() 与匹配检查合并为一步（stack.pop() != 'x'），避免分步判断导致的逻辑遗漏；
前置空栈检查：stack.isEmpty() 在 pop() 前调用，防止 EmptyStackException；
无条件终止：只要任一右括号不匹配，立刻 return false，不依赖后续循环“碰巧清空栈”；
移除冗余长度判断：len % 2 != 0 并非必要（如 "{}" 长度为偶数但 "{" 长度为奇数，后者本就该由栈非空捕获），保留反而可能掩盖逻辑缺陷。

? 测试建议：务必覆盖边界用例：