Interview Prep: Stacks: Part II

Welcome (back) to interview prep. Over these past 3 weeks, we did a quick run-through of the first basic linear data structure which we’ll need knowledge of for technical interviews: linked lists. Here are the links to my two posts:

Linked List Part I
Linked List Part II

Now we’re on the 2nd basic linear data structure: stacks. If you have not already read Part I of stacks or don’t have previous knowledge of the subject, you can read about the basics of stacks in my post here:

Stacks Part I

In this post, now that we know the basics of stack, let’s look at a common algorithm problem involving stacks: Balance the Curly Braces, Brackets and Parens.

This question goes like this:

Given a string consisting of opening and closing curly braces, brackets and parens, determine if they “balance”, that is: does each opening brace, bracket and paren have a “mate” that closes it? If the symbols “balance” return the boolean “true”, if not, return boolean “false.”

Here’s a string of symbols I’ve drawn. Notice how each opening symbol has a “mate.” The algorithm testing this string would return the boolean “true.” So you can see it better, I’ve shown matching pairs by color:

By contrast, here’s a string of symbols that does NOT balanced:

Note how the last coral-colored closing paren on the right end of the string does not have a “mate” and will therefore be evaluated as boolean “false.”

So now let’s design an algorithm in JavaScript to solve this problem.

Let’s draw it out first:

We’ll use a stack data structure, of course. Let’s iterate through the string. When we come upon an opening symbol we’ll simply add it to our stack. Let’s take our balanced stack from the first illustration above. The first five symbols in the string are opening symbols, so we’ll just add them to our stack one at a time like this:

Now on our next iteration of our original string, we come to a closing bracket at position 6. We have to look (peek) at the top of the stack and see if we find its mate--and sure enough we do! That means we can “pop” that opening bracket on the top of our stack:

Here’s what our stack looks like now with the top blue opening bracket removed:

Next stop on our iteration through our original string is position 7, a green-colored closing paren. Is its mate, an opening paren, on the top of the stack? Yes, it is! That means we can pop off that opening paren from the top of our stack. Let’s pop it off and here’s what our stack looks like now:

I won’t go through the rest of the iteration as I’m sure you get the idea!

Let’s Code ‘em Up in JS

/*
 Let's make a helper 'peek' function
that we can use to find the element
on the stack
*/
function peek(stack) {
  return stack[stack.length - 1]
}


function isBalanced(str) {
  let OPENING = "({["
  let CLOSING = ")}]"
  // see FOOTNOTE 1 below:

  // make an empty stack from an array:
  let stack = []

  // iterate through every letter of the string
  for (let i = 0; i < str.length; i++) {

      //store each symbol we visit in the string as variable "letter"
      let letter = str.charAt(i)

      //if the letter we're visiting is part of the OPENING string, 
        // we want to push it onto the stack
      if (OPENING.includes(letter)) {
          stack.push(letter)

        // otherwise, the letter must be a closing symbol...let's see   
          // if it's mate is on top of the stack:
      } else if (CLOSING.includes(letter)) {

          // OOPS!  Before we check for a match, let's check to see that
            // the stack is not empty.  If the stack is empty, there cannot
            //  be a match.  We'll have to return "false"
          if (stack.length === 0) {
              return false

            //  Ok, the stack has something in it, let's check for a match
          } else {
              // grab the symbol on the top of our stack using our 'peek' method
                 // and assign it to variable 'top'
              let top = peek(stack)
               // our top symbol can be found in our OPENING variable
                 //  get the index of our top symbol in the Opening Variable
                 //  and compare it to the index of the letter we're visiting in our CLOSING variable.  
                 //  if the two indicies are THE SAME, we know we have a match and we can pop the top
                 //  item off.
              if (OPENING.indexOf(top) === CLOSING.indexOf(letter)) {
                  stack.pop()
                  // otherwise, we return false, we know we're not balanced
              } else {
                  return false
              }
          }
      }
  }
  //lastly before we end, let's make a final check.  If we really have a balanced
    //  string, it means everything has matched up and all the opening symbols from
    //  the stack have been removed and our stack should be empty
    //  stack.length === 0 will return the final boolean value.
  return stack.length === 0
}


/*
  FOOTNOTE 1
  Regarding these two statements:   
  let OPENING = "({["
  let CLOSING = ")}]"

  variable OPENING contains a string of all possible opening symbols. 
  variable CLOSING contains a string of all possible closing symbols.   

  Notice how the index of opening symbol "("  or [0] in OPENING, is exactly the same index
  as its mate, the symbol ")" or [0] in CLOSING.  

  Index of the opening symbol "{" or [1] in OPENING, is exactly the same index
  as its mate, the symbol "}" or [1] in CLOSING.  

  And so on.  This little correspondence will make it easier for us
  to match up opening and closing symbols--we'll use indicies.
*/

And there you have it! One of the common algorithms asked in coding interviews solved!

Keep studying and keep applying for that amazing job you seek!