Next greater element
June 28, 2017
Check if two node are siblings in a binary tree
August 1, 2017

Check duplicate parenthesis in an expression

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

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