Parenthetically Speaking

#algorithms #career #beginners #interview

I’ve blogged in the past about interesting questions I got asked during interviews, and how to answer them.

In this post, I want to discuss a popular interview question, and how to approach answering it. The reason I want to talk about this specific question is that the algorithm used to solve it is so similar to how a human would approach the same problem.

The Question

The question goes as follows:

Say you have a long string of text, with many parentheses, all nested within each other (for example a very long LISP program). You want to make sure that the sentence is formatted correctly and that every open parenthesis has a corresponding closing parenthesis.

Before I write the solution in code, let’s think a bit about how we, as humans, would approach this problem.

A reasonable approach would be to count all of the opening parentheses and all of the closing parentheses and make sure the numbers are the same.

Let’s try that in JavaScript:

function parenthesesChecker(text) {

  var open = 0
  var close = 0

  for(i = 0; i < text.length; i ++) {
    if(text[i] === "(") {
      open += 1
    } else if(text[i] === ")") {
      close += 1
    }
  }

  return open === close
}

Let’s go through that code line by line.

The first thing we do is, we declare two variables named open and close and we set their value to 0.

Then we iterate over the text, and for every open parenthesis we find we increment the value of open by 1, and for every closing parenthesis, we increment the value of close.

Finally, we check if the values for open and close are the same. If they are we return true, otherwise we return false.

Simple.

Does It Work?

Let’s check out algorithm against a few test strings to make sure it works.

Let’s start with the simplest one: "()"

We have one open parenthesis and one closed one, that returns true. Perfect.

"()()()" returns true as well.

Let’s try some nested parentheses: "((()))", "(()())", "(()(()))" all return true.

Now let’s look at some bad strings and see if they all return false: "(", "(()", "(())()((" all return false, as they should.

But then we run into some problems: ")(" "(()))(" return true even though they are poorly formatted. There is an equal number of open and closed parentheses, but they either start with a closing parenthesis or end with an opening parenthesis.

We could add an if statement to look at the first and last parentheses to check, but what about this case: "())(()"? The first and last parentheses are ok, there’s an equal number of opening and closing parentheses, but it’s still a bad string.

We Need A New Approach.

Let’s think again, how would we as humans look at this issue? A better way to do it would be, instead of counting open and closed parentheses, to keep track of how many parentheses remain open. So we go through the sentence, every time we get to an open parenthesis, we say “that’s one open,” “that’s two open,” etc. and every time we reach a closing parenthesis we count down: “that’s one open,” “no open,” etc. If we ever get below zero, we know we are in trouble, and if we reach the end with parentheses still open we know we are in trouble as well.

How would that look in JavaScript? Very similar to our last function:

function parenthesesChecker(text) {

var open = 0

for(i = 0; i < text.length; i ++) {
    if(text[i] === "(") {
      open += 1
    } else if(text[i] === ")") {
      open -= 1
    }
    if(open < 0)
      return false
  }

  return open === 0
}

The only difference is that instead of tracking two variables, open and close, we only track one variable named open. When we reach an open parenthesis, we increment our open variable, and when we reach a closing parenthesis, we decrement it. If the value of open ever goes below 0 we return false automatically, and if at the end it’s anything OTHER than 0 we return false as well.

This solution seems to work for all cases. If I missed anything, I’m sure you’ll point it out in the comments.

This article has been cross-posted from my blog Coding Hassid.
You can read more about my coding journey there, or by following me on Twitter @yechielk

Top comments (6)

Florian Rohrer • Oct 28 '17

I like this, because this is one of the classical problems that you learn in introduction to formal methods of computer science. In order to determine, if a string is well-balanced, you need a grammar that is at least context-free. A regular grammar, does not suffice.

Implementing a context-free grammar, can be done using a stack. So you can also solve this problem using a stack. Whenever you encounter a (, push it onto the stack. Whenever you encounter a ), pop a ( from the stack. If there is no ( on the stack when you try to pop one, return false. If the stack is not empty when you are done processing the string, return false. Otherwise, the string is well-balanced.

tbodt • Oct 27 '17 • Edited

Back in the day, before paren matchers were a thing, people would stare at their Lisp code, carefully counting: 1, 2, 3, 2, 3, 2, 1, 0 for ((()())). If you didn't end up with zero, there was a problem somewhere.