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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
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..