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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s