Given an expression. Write a program to check whether the given expression is balanced or not.
Sample Input:
{ [ ( ) ] }
Output:
True
Sample Input - 2
{ [ } ]
Output:
False
Sample Input - 3
{ { [ ]
Output
False
Try to solve the problem in O(n) before looking into the solution
Solution:
This problem is so simple. For every opening brackets, you have to check whether the corresponding closing brackets are present in order.
We can solve this problem using Stack. If you want a recap about stack no problem take a look at
this.
First, we start by iterating through the string and if we find an opening bracket we push it to the stack. And if we find a closing bracket we are popping the top element from the stack to check whether the closing bracket is associated with the opening bracket (top element popped). If not, we are returning false or else we continue.
And remember after iterating through the entire string, we have to check the size of the stack. If the size of the stack is not zero (i.e) not empty it means that some closing brackets are missing.
If you don’t get it stay with me :)
