求Java工具类：校验括号优先级与闭合合法性

实现思路 #

用栈结构处理括号匹配，同时在压入左括号时校验嵌套优先级：

• 括号优先级层次：{ > [ > (
• 嵌套规则：
  • (的外层只能是[或(，不能直接嵌套在{内
  • [的外层只能是{或[，不能嵌套在(内
  • {的外层只能是{，不能嵌套在[或(内
• 所有括号必须正确闭合，非括号字符直接忽略

代码实现 #

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class ParenthesesValidator {

    // 右括号到对应左括号的映射
    private static final Map<Character, Character> CLOSE_TO_OPEN = new HashMap<>();
    // 每个左括号允许的外层左括号集合
    private static final Map<Character, Set<Character>> ALLOWED_OUTER = new HashMap<>();

    static {
        CLOSE_TO_OPEN.put(')', '(');
        CLOSE_TO_OPEN.put(']', '[');
        CLOSE_TO_OPEN.put('}', '{');

        ALLOWED_OUTER.put('(', new HashSet<>(Arrays.asList('[', '(')));
        ALLOWED_OUTER.put('[', new HashSet<>(Arrays.asList('{', '[')));
        ALLOWED_OUTER.put('{', new HashSet<>(Collections.singletonList('{')));
    }

    /**
     * 校验字符串中的括号是否符合优先级规则且闭合合法
     * @param s 待校验的字符串
     * @return 合法返回true，否则返回false
     */
    public static boolean isValidParentheses(String s) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            // 处理左括号
            if (CLOSE_TO_OPEN.containsValue(c)) {
                if (!stack.isEmpty()) {
                    char top = stack.peek();
                    // 校验当前左括号是否允许嵌套在栈顶左括号内
                    if (!ALLOWED_OUTER.get(c).contains(top)) {
                        return false;
                    }
                }
                stack.push(c);
            }
            // 处理右括号
            else if (CLOSE_TO_OPEN.containsKey(c)) {
                // 栈空或括号不匹配则非法
                if (stack.isEmpty() || stack.pop() != CLOSE_TO_OPEN.get(c)) {
                    return false;
                }
            }
            // 非括号字符直接忽略
        }

        // 遍历结束后栈必须为空，否则存在未闭合的左括号
        return stack.isEmpty();
    }

    // 测试示例
    public static void main(String[] args) {
        // 合法用例
        System.out.println(isValidParentheses("[a(b)c]"));          // true
        System.out.println(isValidParentheses("{a[b(c)d]e}"));      // true
        System.out.println(isValidParentheses("(abc)"));            // true
        System.out.println(isValidParentheses("{a}+[b]+[c]+(d)"));  // true
        System.out.println(isValidParentheses("{a[b]c}"));          // true
        System.out.println(isValidParentheses("{a[b[c(d)e]f]g}"));  // true

        // 非法用例
        System.out.println(isValidParentheses("(a[b{c}d]e)"));      // false
        System.out.println(isValidParentheses("{9+{(3-3)}+1}"));    // false
    }
}

代码说明 #

1. 初始化映射集合：

   • CLOSE_TO_OPEN：存储右括号与对应左括号的匹配关系，用于快速校验右括号是否匹配栈顶左括号
   • ALLOWED_OUTER：存储每个左括号允许的外层左括号集合，用于校验嵌套优先级

2. 遍历处理字符：

   • 遇到左括号时，先检查栈顶左括号是否允许当前左括号嵌套，合法则压入栈
   • 遇到右括号时，检查栈是否为空或栈顶左括号是否匹配，不合法直接返回false
   • 非括号字符不做处理

3. 最终校验：遍历结束后栈必须为空，确保所有左括号都有对应的右闭合括号

内容的提问来源于stack exchange，提问作者Developer