括号检查器

Question

给定一个表达式字符串 x。检查 exp 中

{,},(,),[,]

的对和顺序是否正确。 例如，该函数应为 exp =

[()]{}{[()()]()}

返回“true”，为 exp =

[(])

.

返回“false”

我正在使用 ArrayList 来解决这个问题。但是我得到了一个 ArrayIndexOutOfBoundsException。
注意：它可以通过 Stack 实现，但我想知道使用我的方法的解决方案。

这就是我尝试做的：

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
    }
}

Answer 1

这个问题的关键是遍历字符串并在删除匹配对的同时跟踪左括号。在迭代结束时，store 应该是空的，表示所有的开头参数都匹配了。在您的解决方案中，您不断添加，但永远不会从中删除：

class Solution {
    // Match opening a closing parentheses
    private static Map<Character, Character> parens = 
        Map.of(')', '(', ']', '[', '}', '{');

    private static Set<Character> openers = new HashSet<>(parens.values());   
    private static boolean isOpener(char c) {
        return openers.contains(c);
    }

    //Function to check if brackets are balanced or not.
    static boolean ispar(String x) {
        // Optimization: check that X has an even length:
        if (x.length() % 2 != 0) {
            return false;
        }
        List<Character> store = new LinkedList<>();
        for (int i = 0; i < x.length(); ++i) {
            char c = x.charAt(i);
            if (isOpener(c)) {
                store.add(c);

                // Optimization: there are more opening parentheses
                // than characters left in the string
                if (store.size() > x.length() - i) {
                    return false;
                }
            } else {
                char matching = parens.get(c);
                if (!store.get(store.size() - 1).equals(matching)) {
                    // Wrong opening character for this closing character
                    return false;
                }
                store.remove(store.size() - 1);
            }
        }
        return store.size() == 0;
    }
}