Data Structure Interview question - Write an algorithm to check for balanced parentheses in a String

A while back I had a difficult interview. It was during COVID-19, so granted it was via a Zoom call which I had to take from a remote room that had no air conditioning. It was my first software engineering related interview,  so I got so nervous, sweating and shocked, that I didn't manage to answer the question like I hoped to.

Anyone who knows me personally, knows that I never had any official programming training, and everything I know I picked up on the job, studied by myself or just spent hours cracking in front of various resources found online. Learning is a huge passion for me, It makes me feel "Armed", and it is my biggest motivation.

But excuses aside, I did't do well, and it bothered me, so I decided to spend the next weekend understanding the task deeper. 

In this post, we are going to cover a common data structure algorithm question.

"Write an algorithm that checks for balanced parentheses in a given String".

How do we "Attack" this question?

Well first of all, let's understand the requirement: 

"Balanced parentheses" means that you have the same amount of opening and closing brackets in a String.

For Example:

A valid String:

'Abc((dE(12)f)ghi)'

'(())()()((()))'

'123()abcd'

Invalid String:

'aBc((def)'

//In this case the first bracket is a closing one, so this String would be invalid.

'123)d(e)f(g)' 

So, first of all we need to write a function that would accept a String as an argument.

Secondly, we need to understand that we have to iterate through the characters of the given String.

So, up to now, our solution would look something like this:

Secondly, we need to understand what should we check for. In our case, our function should return true if the count of the opening brackets is equal to the count of the closing brackets.

So, how can we check for the count of these brackets? 

First of all, there is more than 1 correct answer to each of these questions. In our case, we are going to use something called a "Stack". 

Stacks, are a very useful data structure that allow us to add and remove values from it using the push() and pop() methods. Stacks follow a Last in - First out principle, for example:

 

Now, let's see how we can harness stacks to solve this dilemma.

So, as we said, the function we created need to receive a String argument. 

Then, it needs to iterate over the String and check the following:

• If the current character is an opening bracket "(" - it needs to push() an entrance to the Stack.
• Each time it encounters a closing bracket ")" - it needs to pop() one entrance of the stack.

Basically - each time we open a bracket we add an element to the stack, each time there is a closing bracket - we remove an element from the stack. Finally, there should be no elements left in the stack if the number of the opening and closing brackets is in -fact balanced. 

• If the first encountered bracket is a closing bracket ")" and there are no elements in the stack, it needs to return false and exit the function.
• Finally, the function needs to check if the stack is empty. If so, it needs to return true, if not - false.

I will start with a pseudo code that will describe what we want to check:

And finally, it's time to implement what we came up with as code...

One of the main reason for me maintaining my blog, is for learning and knowledge sharing purposes. 

Each time I learn something new, I like to write about it. The reason for that is that I believe it helps me understand the subject deeper. I think that if you cannot explain a subject in a clear and simple fashion, It means that you don't understand it fully yourself. 

As for this question, as I mentioned, there are more than 1 way to solve this issue, found a better way? I would be happy to learn from you and improve. 

I hope you liked reading this post, see you in the next one.