Algorithm Time: Check for Balanced Parentheses in an Expression Using Stacks

This is an algorithm I was exposed to fairly early on in my bootcamp. At the time, I was completely baffled as to how I might do it. Here's the challenge.

You are provided with a string of parentheses, such as "()()((()()()()()", ")()", or "((()))(()()(())())". You must determine whether or not the string is balanced. That is, whether each opening paren has a closing paren.

The solution to this, it turns out, becomes very simple if you know how to implement a stack! There are so many many things that are very simple once you know the trick of them, but until you do, you might not be able to make the leap. Here I'm going to lay out how I use a Stack to solve this problem. (This isn't a blog post about what Stacks are, so I suggest checking out a description like this one if you're unfamiliar).

This is obviously not the only way to solve this challenge, but it's a pretty efficient one; it should come to O(n). If there's a way to get the answer with O(1) I'd love to have someone show me! But I'm pretty sure you have to run through each character in the string, which necessitates at least O(n).

At any rate, here goes (All code below is in JavaScript).

First up, we establish our function, and create our stack. We can keep it in a simple array.

function isBalanced(str){
    let stack = [];
};

Next, we are going to drop characters from our string into the stack one at a time. Before I get to the code for that, we'll cover it conceptually. Let's envision our stack like so. (Please excuse my trackpad drawing skills.) Here it is empty:

If our string is ")()(", then we would remove the first character, ")", from the string and drop it into our stack. Now our stack looks like this:

Currently that paren can't pair off with anything, so it stays put in the stack.

We'll be doing this with every character in the string, so lets go ahead and code a loop:

function isBalanced(str){
    let stack = [];
    while (str != "") {
        stack.push(str.slice(0, 1)) // remove the first character from the string 
                                // and add it to the end of our stack array
        str = str.slice(1, str.length) // modify original string 
    };
};

We repeat the process with the next character, and get the same result. It's not until we've put the first three characters in that we see a pair appear:

Comparing the top two items, they pair up as "()", so we can now remove them from the stack:

Let's add the code for this process to our function.

function isBalanced(str){
    let stack = [];
    while (str != "") {
        stack.push(str.slice(0, 1)) // remove the first character from the string 
                                // and add it to the end of our stack array
        str = str.slice(1, str.length) // modify original string 
        if ( (stack[stack.length - 1] === ")") && stack[stack.length - 2] === "(" ) {
            // if the last two elements in the stack array are "()", remove them
            stack.pop()
            stack.pop()
        };
    };
};

The way our loop works, this process will repeat until we have added every character from the string to the stack one at a time. Any valid pairs will be removed, leaving us with one of two results. Either the stack is now empty, in which case we know the string was balanced. Or, the stack still has some characters in it, in which case we know the string was not balanced.

With the string we've been using as an example, ")()(", we are left with the following in our stack:

Since this is equivalent to ")(" it is not a valid pair, and won't be removed. Now we have our answer! Let's add a return statement to our function.

function isBalanced(str){
    let stack = [];
    while (str != "") {
        stack.push(str.slice(0, 1)) // remove the first character from the string 
                                // and add it to the end of our stack array
        str = str.slice(1, str.length) // modify original string
        console.log(stack)
        if ( (stack[stack.length - 1] === ")") && stack[stack.length - 2] === "(" ) {
            // if the last two elements in the stack array are "()", remove them
            stack.pop()
            stack.pop()
        };
        console.log(stack)
    };
    if ( stack.length == 0) {
        return true; // the string is balanced
    } else {
        return false; // the string is not balanced
    };
};

That should do it! To sum up, remove characters from the start of the string one at a time, adding them to the stack. Check with each addition to see if the top two cancel each other out, and remove accordingly. Once you run out of characters to add, you should have your result!