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 ‘)’.


Download   Run Code


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 🙂

Get great deals at Amazon

Leave a Reply

newest oldest most voted
Notify of
Top Coder
Top Coder