Find if an expression has duplicate parenthesis or not
Given an balanced expression, find if it contains duplicate parenthesis or not. A set of parenthesis are duplicate if same subexpression is surrounded by multiple parenthesis.
Examples:
Below expressions have duplicate parenthesis  ((a+b)+((c+d))) The subexpression "c+d" is surrounded by two pairs of brackets. (((a+(b)))+(c+d)) The subexpression "a+(b)" is surrounded by two pairs of brackets. (((a+(b))+c+d)) The whole expression is surrounded by two pairs of brackets. Below expressions don't have any duplicate parenthesis  ((a+b)+(c+d)) No subsexpression is surrounded by duplicate brackets. ((a+(b))+(c+d)) No subsexpression is surrounded by duplicate brackets.
It may be assumed that the given expression is valid and there are not any white spaces present.
The idea is to use stack. We iterate through the given expression and for each character in the expression, if the character is a open parenthesis ‘(‘ or any of the operators or operands, we push it to the stack. If the character is close parenthesis ‘)’, then pop characters from the stack till matching open parenthesis ‘(‘ is found. However if the immediate pop hits is open parenthesis ‘(‘, then we have found a duplicate parenthesis. For example, (((a+b))+c) has duplicate brackets around “a+b”. When we reach second “)” after a+b, we have “((” in the stack. Since the top of stack is a opening bracket, we conclude that there are duplicate brackets..
Below is C++ implementation of above idea :

// C++ program to find duplicate parenthesis in a
// balanced expression
#include <iostream>
#include <stack>
using
namespace
std;
// Function to find duplicate parenthesis in a
// balanced expression
bool
findDuplicateparenthesis(string str)
{
// create a stack of characters
stack<
char
> Stack;
// Iterate through the given expression
for
(
char
ch : str)
{
// if current character is close parenthesis ')'
if
(ch ==
')'
)
{
// pop character from the stack
char
top = Stack.top();
Stack.pop();
// if immediate pop is a open parenthesis '(',
// we have found duplicate
if
(top ==
'('
)
return
true
;
// else we continue popping characters from the
// stack till open parenthesis '(' is encountered
else
{
while
(top !=
'('
)
{
top = Stack.top();
Stack.pop();
}
}
}
// push open parenthesis '(', operators and
// operands to stack
else
Stack.push(ch);
}
// No duplicates found
return
false
;
}
// Driver code
int
main()
{
// input balanced expression
string str =
"(((a+(b))+(c+d)))"
;
if
(findDuplicateparenthesis(str))
cout <<
"Duplicate Found "
;
else
cout <<
"No Duplicates Found "
;
return
0;
}
Output:
Duplicate Found
Time complexity of above solution is O(n).
Auxiliary space used by the program is O(n).
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide