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