Balanced Parentheses Problem
I attempted this question a while back and was ultimately stumped. Last week, when I was researching for my post, Applications of Stacks and Queues, I had an epiphany. I could definitely use a stack for this problem!
The problem asks you to check if a string containing parentheses is “balanced”, meaning is each open parenthesis /(/ met with/balanced out by a closed parenthesis /)/? Return true if it is and false if it isn’t. The problem is available on codewars, if you want to take a swing at it yourself (That’s the one I solved for this post). Another variation is on hackerrank which expects you to take into account all three types of brackets /{[(/ and /)]}/.
Initially, I thought about some kind of counter but quickly I saw that was not feasible. After reading about stacks and the First In Last Out principle it follows, it seemed perfect for this problem. Each time we encounter a open parenthesis we push to the stack and pop one off the top of the stack each time we encounter a closed parenthesis as we iterate through the string. So that seems easy enough. The next thing is that in order for any balancing the string’s length needs to be non-empty and even so if the input string is odd or empty, we know right off the bat that it is can’t be balanced. The next thing to consider is if the stack is empty after completely iterating over the string if it isn’t then the output should be false.
We also need to handle if the there are instances where there are more closing brackets than open brackets. In that case, the iteration should just stop and the function should output false because it would be trying to remove elements from an empty stack. Below is my solution in JavaScript.
