Parenthesis matching using stacks

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.

Analysis

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:


Code

Complexity Analysis

Complexity of parenthesis matching algorithm is O(N) time to scan N length string and O(N) extra space for stack.

Test cases

1. ((()))
True

2. ()))
False

3. )(((
False

4. (
False

5 Empty string
True

6. NULL pointer
False

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s