Find duplicate parenthesis in an expression

Given an balanced expression that can contain opening and closing parenthesis, check if the expression contains any duplicate parenthesis or not.


For example,

Input:  ((x+y))+z
Output: Duplicate () found in sub-expression ((x+y))

Input:  (x+y)
Output: No Duplicate () is found

Input:  ((x+y)+((z)))
Output: Duplicate () found in sub-expression ((z))

We can use a stack to solve this problem. The idea is to traverse the given expression and

  • If the current character in the expression is a not a closing parenthesis ‘)’, then we push the character into the stack.
  • If the current character in the expression is a closing parenthesis ‘)’, we check if the topmost element in the stack is an opening parenthesis or not. If it is opening parenthesis, then the sub-expression ending at current character is of the form ((exp)) else we continue popping characters from the stack till matching ‘(’ is found for current ‘)’.

C++ implementation –

Download   Run Code


The expression have duplicate parenthesis

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

Suggested read:
Find all strings of given length containing balanced parentheses
Find all combinations of non-overlapping substrings of a string

Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Notify of
Sort by:   newest | oldest | most voted
Top Coder
Top Coder