### Checking for balanced parentheses using the stack

Posted on

So this problem, looks to see if there is a balance between round, curly, and square brackets.

First up lets discuss the the brackets:

• ( ) Round Brackets
• [ ] Square Brackets
• { } Curly Brackets

Balance can be like so

• (){}[]
• ([{}])
• (((((((((())))))))))

But this is unbalanced

• ( ] ) [   notice closing square bracket without partner
• ( [ ) ]   notice how the curved bracket closes before square bracket closes

If given a string of brackets, how can we tell if it validly pairs up? How can we solve this?

Use an array and every time we we don’t find a matching pair, add the element. If we do find a matching pair of the current element we are looking at and the previous one then pop the match.

What are you talking about?

• (){}[]
• ([{}])
• (((((((((())))))))))

Looking at the above examples, you will eventually come across a pair of matching characters that are next to each other, and as we eliminate them, it frees up other pairs to be matched.

Please explain:

Ok, we will go over this step by step.

Lets loop over the string, removing matches as we find them. Only looking at last added element in array

• string: ([{}]) . array or “stack” : []
• string: ({ } ] )  array: []    no match in queue, add to queue
• string: ( [ { } ] )  array: [ (  ]   no match in queue, add to queue
• string: ( [ {] )  array: [ ( [  ]   no match in queue, add to queue
• string: ( [ { } ] )  array: [ ( [ { ]   match in queue, remove from queue
• string: ( [ { } ] )  array: [ ( [  ]   match in queue, remove from queue
• string: ( [ { } ] )  array: [ (   ]   match in queue, remove from queue
• string: ( [ { } ] )  array: [  ]   string traversed nothing in  queue

Here is a REPL in case you wanted to play with the code

Advertisement