# Parenthesis Matching using Stacks

[wpdm_package id=’1339′]

Algorithm:

- Create a Stack.
- while(end of input is not reached) {

- if the character read is not a symbol to be balanced, ignore it.
- if the character is an opening symbol like (, {, [, push it onto the stack.
- If it is a closing symbol like ), }, ], then if the stack is empty report an error. Otherwise pop the stack.
- If the symbol popped is not the corresponding opening symbol, report an error.

}

- At the end of the input, if the stack is not empty report an error.

[sourcecode lang=”cpp”]

for(int i=0;i<exp.length();i++)

{ if(exp[i]=='(‘||exp[i]=='[‘||exp[i]=='{‘)

mystack.push(exp[i]);

if(exp[i]==’)’||exp[i]==’]’||exp[i]==’}’)

{ if(mystack.empty())

{ cout<<"Not a valid expression";

break;

}

else

{ char ch=mystack.top();

if(ch=='(‘)

{ if(exp[i]!=’)’)

{ cout<<"Not a valid expression";

break;

}

}

if(ch=='{‘)

{ if(exp[i]!=’}’)

{ cout<<"Not a valid expression";

break;

}

}

if(ch=='[‘)

{ if(exp[i]!=’]’)

{ cout<<"Not a valid expression";

break;

}

}

mystack.pop();

}

}

}

if(!mystack.empty())

cout<<"Not valid expression";

[/sourcecode]