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

## Java

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

Find all strings of given length containing balanced parentheses

Find all combinations of non-overlapping substrings of a string     (1 votes, average: 5.00 out of 5) Loading...

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 🙂  