如何用栈正确判断括号字符串的有效性-java教程-PHP中文网

如何用栈正确判断括号字符串的有效性

本文详解括号匹配问题的正确解法：指出常见错误思路（如错位索引、忽略嵌套）的根本缺陷，并完整实现基于栈的高效验证算法，支持 (), {}, [] 三类括号的嵌套与顺序校验。

本文详解括号匹配问题的正确解法：指出常见错误思路（如错位索引、忽略嵌套）的根本缺陷，并完整实现基于栈的高效验证算法，支持 `()`, `{}`, `[]` 三类括号的嵌套与顺序校验。

你提供的代码试图通过“配对位置检查”来验证括号有效性，但存在两个关键逻辑错误，导致连最简单的 "()" 都返回 false：

索引越界与错位访问：s.charAt(2 * index + 1) 和 s.charAt(2 * index + 2) 在 index = 0 时分别访问下标 1 和 2，而字符串 "()" 长度仅为 2，下标最大为 1 —— 这直接引发 StringIndexOutOfBoundsException（或在某些运行环境下静默出错）。更根本的是，charAt() 的索引从 0 开始，而非 1，因此你的配对逻辑完全错位。
无法处理嵌套结构：该方法仅检查相邻偶数位与奇数位的“硬配对”，假设所有括号都是并列平铺的（如 "()[]"），但真实场景中大量存在嵌套（如 "[()]"、"{[()]}"）。这类结构要求“后开先闭”，必须依赖后进先出（LIFO）语义——而这正是栈（Stack） 的天然优势。

✅ 正确解法：使用栈模拟括号的入栈与匹配出栈过程

一点妙笔

一款AI工具，主要用于体制内必备 AI 公文写作助手，适合需要提升相关任务效率的用户。

下载

遍历字符串每个字符：
- 若为左括号 (、{、[ → 入栈；
- 若为右括号 )、}、] → 检查栈顶是否为对应左括号；若不匹配或栈为空，则无效；
遍历结束后，栈必须为空才算完全匹配。

以下是 Java 标准实现（含清晰注释）：

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        // 使用 Deque 作为栈（比 Stack 更推荐，线程安全且性能优）
        Deque<character> stack = new ArrayDeque();
        // 定义右括号到左括号的映射，便于快速匹配
        Map<character character> pairs = Map.of(
            ')', '(',
            '}', '{',
            ']', '['
        );

        for (char c : s.toCharArray()) {
            if (pairs.containsValue(c)) {
                // 左括号：直接入栈
                stack.push(c);
            } else if (pairs.containsKey(c)) {
                // 右括号：检查栈顶是否匹配
                if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                    return false;
                }
            }
            // 字符非法（题目保证只含括号，此处可省略校验）
        }

        // 所有括号匹配完毕，栈应为空
        return stack.isEmpty();
    }
}</character></character>

? 关键注意事项：