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

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

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

excellent..

wpDiscuz