Parenthesis matching problem
Problem is given a string of parenthesis ‘(‘ 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.
Parenthesis matching a typical problem where stacks are used.
For asserting that the current closing parenthesis is in sync with what we have already seen, we just need to check if current parenthesis completes a pair with opening parenthesis we last seen.
Next closing parenthesis should complete pair with the one prior to last and so on.
So we see the pattern here that we need to check the opening parenthesis we encountered last. What is the data structure we use for that? Stack of course.
Algorithm for parenthesis matching
- Whenever we see a opening parenthesis, we put 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.
Watch video here:
Complexity of parenthesis matching algorithm is O(N) time to scan N length string and O(N) extra space for stack.
5 Empty string
6. NULL pointer