## DEV Community is a community of 848,701 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Yechiel Kalmenson

Posted on • Originally published at blog.yechiel.me on

# Parenthetically Speaking

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.

## Discussion (6) Florian Rohrer

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 • Edited on

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. Yechiel Kalmenson

Yup, that's what my algorithm basically does :) Yechiel Kalmenson

Thanks for sharing! Peter Kim Frank

Great step-by-step breakdown. Big fan of these contained posts that use code snippets to walk through #beginners concepts. Thanks for sharing!