Jun 292017
 

A valid mathematical expression can also have duplicate parenthesis as shown below:

((a+b))
(((a+(b)))+(c+d))

Write code to find if an expression has duplicate parenthesis. You may assume that expression does not have any white spaces.

Such questions usually use a Stack. Below is the algorithm:

Traverse given expression and for each character:
 - If it is open parenthesis ‘(‘, an operator or an operand, push it to the stack. 
 - If it is close parenthesis ‘)’, Then pop an element from Stack, if immediate pop hits is open parenthesis ‘(‘, then we have found a duplicate parenthesis. Else, pop all characters from the stack till matching open parenthesis ‘(‘ is found. 

Below is C++ implementation of above idea. It use the linked list implementation of Stack. Except that we are using a stack of characters and not integers.

Code

bool findDuplicateparenthesis(char* str)
{
  MyStack stack;

  // TRAVERSE THE EXPRESSION  
  for(char ch; ch != '\0'; str++)
  {
    ch = *str;
    
    if (ch == ')')
    {
      char top = stack.pop();
      
      // IF IMMEDIATE pop IS OPEN PARENTHESIS '(',
      if (top == '(')
        return true;
      else
      {
        while (top != '(')
        {
          top = stack.pop();
        }
      }
    }
    else
      stack.push(ch);
  }
  
  // NO DUPLICATES
  return false;
}

This function takes O(n) time and O(n) memory

 

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)