JavaScript Coding Challenge: "Regular Brackets" - follow up

I promised in the last article that we’re going to have a look at how to solve the Regular Brackets problem with multiple types of brackets, and as I said last time we’re going to use a data structure called: the STACK. 😄

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed. The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out). Wikipedia.

In JavaScript we already have the array data structure which has the push and pop methods. This is perfect for what we need.

First let’s create the function, which receives a string of brackets (noted b for simplicity):

function regularBracketsSequence2(b) {}

Now… let’s add the empty stack and again a simple for loop to check each bracket:

function regularBracketsSequence2(b) {
    var stack = [];
    for (var i = 0; i < brackets.length; i++) {}
}

Great! Let’s talk a little bit now about why do we use a stack for this challenge, and how does it help.

As you might have already thought, a simple integer count won’t help this time as it did last time when we only had one type of brackets, so we’ll use a stack to store each opening bracket in it, of any type. This way when we encounter a closing bracket we can check if it is of the same type. If it is, we pop the last item from the array as we found the matching pair, otherwise if it is an opening bracket, we push it in the stack.

We also need to check if we encounter a closing bracket before an opening one, if that’s the case, than we already know that the sequence isn’t correct.

function regularBracketsSequence2(b) {
    var stack = [];
    for (var i = 0; i < b.length; i++) {
        if (b[i] === '(' || b[i] === '[' || b[i] === '{') {
            stack.push(b[i]);
        } else if (
            (b[i].length > 0 &&
                b[i] === ')' &&
                stack[stack.length - 1] === '(') ||
            (b[i] === ']' && stack[stack.length - 1] === '[') ||
            (b[i] === '}' && stack[stack.length - 1] === '{')
        ) {
            stack.pop();
        } else {
            return false;
        }
    }
    return stack.length === 0;
}

At the end we check if the stack is empty, because there might be a chance to have more opening brackets than closing ones, which is also not allowed! 🙂

Conclusion

The stack data structure is very powerful. It’s used in many algorithms and is a must know for every developer.

Now you are prepared to face this challenge in any interview. As you can see it’s pretty straightforward.

I wish you all the best for your next interview!

Happy coding! 😇