Parenthesis Checker

Question

Given an expression string x. Examine whether the pairs and the orders of {,},(,),[,] are correct in exp. For example, the function should return 'true' for exp = [()]{}{[()()]()} and 'false' for exp = [(]).

I am using an ArrayList to solve that. But I'm getting an ArrayIndexOutOfBoundsException.
Note: It can be implemented by Stack but I want to know the solution using my approach.

This is what I tried to do:

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

Please edit the question to include an exact copy of the error message. Please do that using copy-and-paste. While you are at it, please indicate which line the error occurs. — Old Dog Programmer, Mar 27 '23 at 18:35
If this comes from a coding practice / challenge site, please include a link to the page. — Old Dog Programmer, Mar 27 '23 at 18:37
If you want to become a software developer, you will need to have some debugging skills. This can be a problem to practice debugging. One way to debug a small program like this is to pretend you are the computer. You can use pen and paper for the memory. Another is to use a debugger, often included with an IDE. The debugger allows you to follow the code one-line-at-a-time, and lets you monitor the values of variables. A third tool is to put `System.out.println` in the code to give you the needed information. — Old Dog Programmer, Mar 27 '23 at 18:43
If the error is, in fact, an `ArrayIndexOutOfBoundsException`, then it shouldn't be coming from the code you've shown, as this code doesn't use arrays. A mistake in indexing an `ArrayList` would result in an `IndexOutOfBoundsException`. Please edit the question to show a [minimal, complete and verifiable example](https://stackoverflow.com/help/minimal-reproducible-example). — Old Dog Programmer, Mar 27 '23 at 19:20
I hope this is off-topic. But, it is possible for `ArrayList` to throw an `ArrayIndexOutOfBoundsException` if the ArrayList is accessed by more than one thread without proper synchronization: https://stackoverflow.com/questions/9632387/arraylist-add-throws-arrayindexoutofboundsexception — Old Dog Programmer, Mar 27 '23 at 22:04

Mureinik · Answer 1 · 2023-03-27T19:45:40.520

The key to this problem is to iterate over the string and keep track of the opening parentheses while removing the matching pairs. At the end of the iteration, the store should be empty, signifying that all the opening parentheses are matched:

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

Parenthesis Checker

1 Answers1