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++

Download   Run Code

Java

Download   Run Code

Output:

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Top Coder
Guest

excellent..