Checking for balanced parentheses using the stack
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
vSPARROW 