balancedParens: a toy problem review

Chris Abrami
Jul 24, 2017 · 8 min read

It’s no secret that there are certain toy problems that are extremely popular in an interview setting, and balancedParens seems to be one of them. So let’s take some time to review it.

The first clarification that must be made on this problem is actually what is meant by ‘parentheses’. Technically, only ‘(‘ and ‘)’ are parentheses. When solving this problem we’re going to make the assumption that we’re checking for balanced parentheses, square brackets [ ] and curly braces { }. For this discussion when I mention ‘parentheses’ I’ll be referring to all three unless I specifically break them out.

Let’s chat briefly before diving in about what this algorithm is actually doing. This algorithm is really a utility function that checks whether parentheses are balanced or not. In terms of usage, it has more in common with a grammar check than with an algorithm that does things like manipulate an input (such as a sorting algorithm).

In a real world setting, the input is likely to be some code that we want to check, just like we’d run a Word document through a spelling and grammar check. The algorithm will return true if the parentheses in the input are balanced, and will return false otherwise. Again, unless noted otherwise, by ‘parentheses’ I am referring to ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, and ‘}’.

Our algorithm is going to assume that we’ve taken our code and translated it into a string. For academic purposes, we’re going to look mostly at strings containing exclusively different types of parentheses. We’ll build functionality into the algorithm that skips over anything in the string that isn’t an opening or closing parentheses.

EXAMPLE OF WHAT COULD BE PASSED IN:let bubbleSort = (arr) => {
if (!arr || !Array.isArray(arr)) {
return 'please enter in an array of numeric values';
}
let countSwitch;
//set a while loop
while (countSwitch !== 0) {
countSwitch = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i + 1] < arr[i]) {
//do a switch
var firstVal = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = firstVal;
countSwitch ++;
}
}
}
return arr;
};
let bubbleSortString = bubbleSort.toString();balancedParens(bubbleSortString);WE'RE GOING TO PRIMARILY TEST OUR ALGORITHM BY PRIMARILY BY PASSING IN STRINGS COMPRISED ENTIRELY OF PARENTHESES, INCLUDING:'(){}[]'
'()()[]{[]}[({})]'
'((((()))))'
'()[]{'
'(()))'
'((((('

You can likely see that some of these strings are going to pass and others are not. There are a number of ways to craft an algorithm that will return the correct response for the strings above. But many will cease to work when we hit an interesting use case:

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

Does nothing look wrong with it? Take another look

 0  1  2  3  4  5  6  7  8  9  10 11 12 13 
'( ) [ ( { ( ) { [ } ] } ) ]'
^

The issue here is that we’re trying to close an outer parentheses before we’ve closed an inner parentheses. Specifically, we’ve opened a curly brace at index 7, followed by a square bracket at index 8. We then try to close the curly brace in index 9 prior to closing out our square bracket, which we try to do in index 10.

And here is where the solution comes into focus. In order to properly assess the parentheses in this string, whenever we hit a closing parentheses of any type we need to ask ‘is this an appropriate time to be closing this parentheses?’. And the only way to decide that is to track what’s currently opened, and the order in which it’s been opened.

Sounds like a lot but the solution is actually quite straightforward. We’re going to employ a data structure called a stack.

For the uninitiated, think of nesting dolls (thank you, World Market for having these available for sale)!

As many of us know, nesting dolls can be pulled apart and put back together, with the smaller dolls ‘nested’ inside the larger one. If I were to spread the pieces around a table, it would be an easy enough feat to accomplish.

However, what if I couldn’t see the pieces, but had to tell you how to put the doll back together? I could say ‘put the largest top piece and the largest bottom piece together’, ‘put the smallest top piece and the smallest bottom piece together’, etc…but that wouldn’t work. Why? Because in order to nest the dolls properly, the pieces have to be put back together in order. In particular, the pieces would have to be put back together in reverse order to whatever order they were taken apart. And this is where our stack comes in.

Our stack provides us with a ‘road map’ to tell us what we’ve pulled apart so far, in order to get to the most nested place. That way, we know the order in which to put the pieces back together.

Our stack would look like this:

…and could be abstracted like this: [ ‘(‘, ‘{‘, ‘[‘ ]

A ‘balanced’ string would look like this with the dolls:

And could be abstracted like this:

‘({[]})’

Once we’ve gotten to the most nested place, the first thing we’d have to do in order to put the doll back together is to see if the piece matches.

If it does, we pop it off of our stack, leaving our other two pieces remaining:

If the pieces are balanced, we end up with a nicely nested doll. If they’re not then we can’t put the doll back together, at least not in its entirety. As mentioned before, this algorithm works especially well because it deals with the pesky issue where the order of closing parentheses is off, even if all the right pieces are there (as seen with the dolls below):

We know that we can’t put the doll back together in this order. The blue bottom doesn’t ‘fit’ with the red top and can’t be ‘nested’. In the context of our problem, our an example of this might look like:

‘([{]})’

For purposes of simplicity, I’m going to use an array, and the .push() and .pop() methods to mimic the behavior of a stack.

Let’s take a look at the solution code, and walk through it:

balancedParens = (string) => {
let storage = [];
let openings = ['[', '{', '('];
let closings = [']', '}', ')'];
let opposites = {
')': '(',
']': '[',
'}': '{'
};
for (let char of string) {
if (openings.includes(char)) {
storage.push(char);
} else if (closings.includes(char)) {
let opposite = opposites[char];
let lastIndex = storage[storage.length - 1];
if (opposite !== lastIndex) {
return false;
} else {
let popped = storage.pop();
}
} else {
continue;
}
}
if (storage.length > 0) {
return false;
}
return true;
};

storage is where were’ going to store items (i.e. opening parentheses) that we put into our stack.

Now, let’s drop down to the ‘for’ loop. For those unfamiliar with ES6, the ‘for…of’ loop will allow us to loop through characters in a string, without having to manipulate the string in any way.

For each character that we loop through in the string, there are three possibilities:

POSSIBILITY ONE: It’s an opening parentheses, square bracket or curly brace (i.e. ‘(‘, [‘ or ‘{‘ ).

POSSIBILITY TWO: It’s a closing parentheses, square bracket or curly brace (i.e. ‘)’, ‘]’, ‘}’).

POSSIBILITY THREE: It’s some other character.

balancedParens = (string) => {
let storage = [];
let openings = ['[', '{', '('];
let closings = [']', '}', ')'];
let opposites = {
')': '(',
']': '[',
'}': '{'
};
for (let char of string) {
if (openings.includes(char)) { //Possibility One
storage.push(char);
} else if (closings.includes(char)) { //Possibility Two
let opposite = opposites[char];
let lastIndex = storage[storage.length - 1];
if (opposite !== lastIndex) {
return false;
} else {
let popped = storage.pop();
}
} else { //Possibility Three
continue;
}
}
if (storage.length > 0) {
return false;
}
return true;
};

Dealing with possibility three is easy — we don’t care about other characters in the string, so we simply ‘skip’ over this iteration using the continue keyword and move to the next character in the string.

When we hit ‘(‘, ‘[‘ or ‘{‘, (possibility one) we are adding another step to our ‘road map’, which means that we have to tack that step onto the end of our array as the last (or most recent step). We use the .push() method to push to our stack.

The magic of this algorithm occurs in the ‘else if’ block, which deals with possibility two. When we hit either ‘)‘, ‘]‘ or ‘}‘ we know that we’re putting things back together, or at least trying to. We’ve got the steps in our ‘road map’ stored away in our stack, so all we have to do is check whether or not the closing parentheses matches the most recent opening parentheses. In other words, if we iterate over a ‘)’ and the most recent (i.e. last) item in the stack is a ‘(‘, then we’re good to go. They match up and we can clear that ‘step’ off the stack (which we’ll do using the native .pop() method.

There are actually two points in this algorithm when we determine whether or not parentheses are unbalanced. One is at this juncture. If we iterate over a ‘]‘, for example, and the last item in the stack is a ‘(‘ then we automatically know that the parentheses are not balanced and can return ‘false’. Ideally, if everything is balanced, we come across the corresponding closing parentheses in reverse order that we came across the opening parentheses.

When parentheses are balanced, there shouldn’t be anything left in our stack — they should all have been cleared off by the end of the loop. Our storage array should have a length of zero.

Which, of course raises the question of a situation it might not be zero, once the loop is finished running. I offer an example, below:

'(((([{}])'

We won’t run across any issues clearing things off the end of the stack, as they’d be cleared in the right order, but the parentheses will still be unbalanced cause we’ve had more opening parentheses than closing ones. As a result, once the loop is done executing, our stack will still look like this:

[ '(', '(', '(' ]

So we have a second test in our algorithm after the loop is done that simply checks the length of the storage array. If anything (read: extra open parentheses) are left inside, we’ll know that the parentheses are not balanced and can return false.

And that’s it!

Chris Abrami

Written by

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade