### 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.

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

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.

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