Given a balanced expression, find if it contains duplicate parenthesis or not. A set of parenthesis are duplicate if the same subexpression is surrounded by multiple parenthesis
Below expressions have duplicate parenthesis -
((a+b)+((c+d)))
The subexpression "c+d" is surrounded by two
pairs of brackets.
Below expressions don't have any duplicate parenthesis -
((a+b)+(c+d))
No subexpression is surrounded by duplicate
brackets.
: Here the problem is of standard stack problem , let us dry run and understand it ::
Initially My string is ((a+b)+((c+d)))
Step 1:Push all char if it is not ')'
my stack [((a+b]
step 2:Now my string is at ')' , Here the idea is we need to check is there any character except '(' i between prev '(' and present , if the count is 0 , then we can say it is duplicate...
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
stack<char>st;
for(int i = 0;i < s.size();i++){
if(s[i] == ')'){
int count = 0;
int pres = st.top();
st.pop();
while(pres != '('){
pres = st.top();
st.pop();
count++;
}
if(count < 1){
cout << "Duplicate Exists" << endl;
return 0;
}
}else{
st.push(s[i]);
}
}
cout << "No Duplicate Exists" << endl;
return 0;
}