Validate Bracket And Parenthesis Combos Using Stacks

Job interviews for software engineering and other programming positions can be tough. There are too many things to study, and even then it still might not be enough. Previously I had written about a common Fibonacci number algorithm and finding duplicate values in array.

Those skill refreshers were written in JavaScript. This time we are going to take a turn and validate bracket combinations using the Java programming language.

So when I say bracket combinations, what exactly do I mean? Take the following string for example:

String validCombo = "{ [ ( { } [ ] ) ] }";

The above string is valid because each opening and closing bracket aligns correctly. You can ignore the spacing between each bracket because they will be ignored.

An example of an invalid string might look like the following:

String invalidCombo = "{ ( [ ] ] }"

Notice that we are trying to pair a ( with a ] which is not correct.

So how can we attempt to validate such a string in Java? The recommended way would be to make use of the Stack data type. The idea is to add all opening brackets to a stack and pop them off the stack when closing brackets are found. If the closing bracket doesn’t match the top element (last pushed element) of the stack, then the string is invalid. The string is also invalid if it has been iterated through and the stack is not empty in the end.

import java.util.*;

public class Brackets {

    private String brackets;

    public Brackets(String s) {
        brackets = s;
    }

    public boolean validate() {
        boolean result = true;
        Stack<Character> stack = new Stack<Character>();
        char current, previous;
        for(int i = 0; i < this.brackets.length(); i++) {
            current = this.brackets.charAt(i);
            if(current == '(' || current == '[' || current == '{') {
                stack.push(current);
            } else if(current == ')' || current == ']' || current == '}') {
                if(stack.isEmpty()) {
                    result = false;
                } else {
                    previous = stack.peek();
                    if((current == ')' && previous == '(') || (current == ']' && previous == '[') || (current == '}' && previous == '{')) {
                        stack.pop();
                    } else {
                        result = false;
                    }
                }
            }
        }
        if(!stack.isEmpty()) {
            result = false;
        }
        return result;
    }

}

The above code operates with a time complexity of O(n) and to demo it you could do something like the following:

Brackets b = new Brackets("{[({}())]}");
System.out.println("Valid String: " + b.validate());

Conclusion

Balancing parenthesis and brackets is a good interview question because it is one of the first steps to understanding how to parse and validate data. Imagine if you were asked to write a code interpreter or parse JSON. Knowing how to balance or validate brackets and parenthesis will certainly help. Please share your experience with this topic in the comments if you’ve had it as an interview question or if you think you have a better solution than what I’ve come up with.

A video version of this article can be seen below.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in C#, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Unity. Nic writes about his development experiences related to making web and mobile development easier to understand.