Parenthesis Matching using stack

Problem is given a string of parenthesis ‘(‘ and ‘)’ ,'{' and '}' , '[' and ']'  find out if there are matching pairs or not, typically this known as parenthesis matching problem.

For example : ‘((()))’ input will return TRUE, but ‘)(())’ will return FALSE.

Algorithm for parenthesis matching

• Whenever we see a opening parenthesis, we push it on stack.
• When we see closing parenthesis, we check what is at the top of the stack, if we have corresponding parenthesis, we are good. Remove it from the top of the stack. And move on.
• If parenthesis at the top of the stack is not corresponding opening parenthesis, we return false, as there is no point check the string further.
• Again, when we reach at end of the string, we need to check if stack is empty or not. If the stack is empty, we are good. If stack is not empty, parenthesis do not match.

Implementation 

Browse More Articles

Tweet

Written by sutha

We are Creative Blogger Theme Wavers which provides user friendly, effective and easy to use themes. Each support has free and providing HD support screen casting.