In this post we will explore and implement an algorithm which helps us verify that if the brackets are balanced or validly used. This is a very important application of stacks as a lot of programming languages use brackets very extensively in their syntax and one of the job of a compiler is to check if the brackets are balanced or not. For simplicity's sake we will just use a list with the methods append() and pop(). This will help us emulate a stack without actually needing to implement it. If you want to, you can go and learn about stacks on this link.
A set of brackets can be called balanced if all of the brackets in it are properly matched.
Examples of balanced brackets :
Examples of unbalanced brackets :
So now getting to the algorithm, what we simply do is that we go through a string of brackets and check that for every closing bracket there is a properly nested opening bracket.
This is how we do it -
- Convert the input string into a list.
- Traverse the list
- If we see an opening bracket, push it to the stack.
- When we encounter a closing bracket, check if it is equal to the opening bracket that we pop from the stack.
- If the stack is empty, return true. If not, return false.
Comments
Post a Comment