Parenthesis Matching using Stacks

[wpdm_package id=’1339′]

Algorithm:

  • Create a Stack.
  • while(end of input is not reached) {
  1.  if the character read is not a symbol to be balanced, ignore it.
  2. if the character is an opening symbol like (, {, [, push it onto the stack.
  3. If it is a closing symbol like ), }, ], then if the stack is empty report an error. Otherwise pop the stack.
  4. 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]

Leave a Reply

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