使用ArrayList实现括号匹配遇数组越界异常求解决方案

需要实现一个函数，检查给定字符串中的{、}、(、)、[、]是否配对正确且顺序合法。例如输入[()]{}{[()()]()}返回true，输入[(])返回false。

尝试用ArrayList实现该功能时出现ArrayIndexOutOfBoundsException，希望基于ArrayList的思路修复问题，原代码如下：

class Solution {
    //Function to check if brackets are balanced or not.
    static boolean ispar(String x) {
        int n = x.length();
        boolean sol = false;
        ArrayList < Character > store = new ArrayList < Character > ();
        if (n % 2 != 0 && x.charAt(0) == ')' && x.charAt(0) == '}' && x.charAt(0) == ']') {
            sol = false;
        } else {
            for (int i = 0; i < n; i++) {
                if (x.charAt(i) == '[') {
                    store.add('[');
                    store.add(']');
                }
                if (x.charAt(i) == '{') {
                    store.add('{');
                    store.add('}');
                }
                if (x.charAt(i) == '(') {
                    store.add('(');
                    store.add(')');
                }
                if (x.charAt(i) == ')') {
                    store.remove(')');
                    store.remove('(');
                }
                if (x.charAt(i) == '}') {
                    store.remove('}');
                    store.remove('{');
                }
                if (x.charAt(i) == ']') {
                    store.add(']');
                    store.add('[');
                }
            }
            if (store.size() == 0) {
                sol = true;
            }

        }
        return sol;
        // add your code here
    }
}

原代码的问题分析 #

1. 初始判断逻辑错误：n % 2 != 0 && x.charAt(0) == ')' && x.charAt(0) == '}' && x.charAt(0) == ']' 条件永远不成立，单个字符不可能同时等于三个不同的右括号；且长度为奇数时直接不可能配对成功，应单独判断返回false。
2. 左括号处理逻辑错误：遇到左括号时同时添加左右括号到列表，完全不符合括号匹配的后进先出逻辑。
3. 右括号处理逻辑错误：
   • 遇到]时反而添加]和[，逻辑完全颠倒。
   • 使用store.remove(')')按值删除元素，会删除列表中第一个匹配项，而非最后添加的元素，破坏嵌套括号的匹配顺序。
   • 未做存在性检查，当列表为空或元素不匹配时直接删除，会抛出ArrayIndexOutOfBoundsException。

修正后的代码（基于ArrayList模拟栈） #

class Solution {
    //Function to check if brackets are balanced or not.
    static boolean ispar(String x) {
        int n = x.length();
        // 长度为奇数直接返回false，括号无法成对
        if (n % 2 != 0) {
            return false;
        }
        ArrayList<Character> store = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char c = x.charAt(i);
            // 遇到左括号，添加对应的右括号到列表末尾（模拟栈压入预期匹配的右括号）
            if (c == '[') {
                store.add(']');
            } else if (c == '{') {
                store.add('}');
            } else if (c == '(') {
                store.add(')');
            } else {
                // 遇到右括号，检查列表是否为空或最后一个元素是否匹配
                if (store.isEmpty() || store.remove(store.size() - 1) != c) {
                    return false;
                }
            }
        }
        // 遍历结束后列表为空，说明所有括号都正确配对
        return store.isEmpty();
    }
}

代码说明 #

• 先判断字符串长度是否为奇数，是则直接返回false，因为括号必须成对出现。
• 遇到左括号时，将对应的右括号添加到ArrayList末尾，用列表模拟栈的"压入"操作，记录后续需要匹配的右括号。
• 遇到右括号时：
  • 若列表为空，说明没有对应的左括号，直接返回false。
  • 移除列表最后一个元素（模拟栈的"弹出"），并对比是否与当前右括号一致，不一致则说明顺序错误，返回false。
• 遍历完成后，若列表为空则所有括号都正确配对，返回true；否则存在未匹配的括号，返回false。

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