Balanced Parentheses Algorithm

By | May 24, 2014

This is a classic example of how using an appropriate Datastructure can improve the quality of your algorithm.
The Balanced Parentheses or Valid Parentheses is like this :

Given a string containing ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid or not.
[(a+b)+c] is Valid where as (a+b)+c] is Invalid.

The problem is very easy if you use the right data structure Stack in this case .
Here the solution :
Algorithm

  • Initialise a Stack s
  • Travesrse the String str at each char do
    • if val(char) something else that parentheses or null ignore and continue
    • if(null) reached and stack empty return valid
    • if(null) reached and stack not empty return invalid
    • if val(char)==”opening parentheses” push val(char) on stack continue
    • if val(char)==”closing parentheses” check if “Stack.top()== opening parentheses” of same type or not for example for “)” matching parentheses is “(” . A unmatch will occur if type is different like “[“. if match occurs popStack() else return Invalid

Here’s the code for Balanced Parentheses Problem

Have got some interview questions submit it here.So that we can help other candidates like you to land their dream job

Leave a Reply

Your email address will not be published. Required fields are marked *