Check if given expression is balanced expression or not

Given an expression containing opening and closing braces, check if it is balanced or not.

 

For example,


{[{}{}]}[()], {{}{}}, []{}() are balanced expressions.

{()}[), {(}) are not balanced.


 
The idea is to use a stack to solve this problem. We traverse the given expression and

  • If current character in the expression is a opening brace ‘(‘ or ‘{‘ or ‘[‘, we push it to the stack.
     
  • If current character in the expression is a closing brace ‘)’ or ‘}’ or ‘]’, we pop a character from the stack and we return false if the popped character if not an opening brace or it does not pair with current character of the expression. Also if stack is found to be empty, that means the number of opening braces is less than number of closing brace at that point, so expression cannot be balanced.

 
C++ implementation –
 

Download   Run Code

Output:

The expression is balanced

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n). Here, n is the length of the input expression.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂