Given a parentheses expression, check if the pairs and orders of “(“, “)”, “{“, “}”, “[“, “]” are correct in the expression.

Example

Expression	Result
[ ( ) ] { } { [ ( ) ( ) ] ( ) }	Balanced
[ ( ] )	Not Balanced

Solution

After understanding the above problem, we can say that an expression will be balanced if “every opening parenthesis has a closing parenthesis in last opened, first closed order”. This can be computed using a stack. Below is a program in Java to demonstrate this.

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        String[] expressions = {
                "[()]{}{[()()]()}",
                "[(])",
                "}"
        };

        for (String exp : expressions) {
            System.out.println(String.format("%s is %s", exp, checkBalanced(exp) ? "Balanced" : "Not Balanced"));
        }
    }

    private static boolean checkBalanced(String input) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);

            switch (ch) {
                case '(':
                case '{':
                case '[':
                    stack.push(ch);
                    break;

                case ')':
                case '}':
                case ']':
                    if (stack.size() == 0 || !canBePopped(stack.peek(), ch)) {
                        return false;
                    } else {
                        stack.pop();
                    }
                    break;
            }
        }

        return stack.size() == 0;
    }

    private static boolean canBePopped(char stackTop, char ch) {
        if (ch == ')' && stackTop == '(') {
            return true;
        } else if (ch == '}' && stackTop == '{') {
            return true;
        } else if (ch == ']' && stackTop == '[') {
            return true;
        } else {
            return false;
        }
    }
}

[()]{}{[()()]()} is Balanced
[(]) is Not Balanced
} is Not Balanced