I am to write a function for the following:
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.
For example, “((a+b)+((c+d)))” has duplicate parentheses around “c+d”.
My code:
import java.util.Stack;
public class DuplicateParentheses {
public static boolean isduplicate(String str){
Stack<Character> s = new Stack<>();
for(int i =0 ; i<str.length() ; i++){
char curr = str.charAt(i);
if(curr == ')'){
int count = 0;
while(s.peek() != '('){
s.pop();
count++;
}
s.pop();
if(count==0){
return true;
}
}else{
s.push(curr);
}
}
return false;
}
public static void main(String[] args) {
String str = "((a+b)(+)(c+d))";
System.out.println(isduplicate(str));
}
}
It returns the wrong result for the following input: “((a+b)(c+d))”
The output should be false, but my code is returning true.
According to the logic of my code I expected it to return a correct result. What is the mistake?
Tanush Garg is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
Your code does not check whether there are two consecutive closing parentheses before it performs return true. Secondly, checking whether the count of non-opening parentheses you pop from the stack is zero is not a sound indication that there were two consecutive opening parentheses that relate to the last two closing parentheses.
My guess is you got this algorithm from reading the GeeksforGeeks article Find if an expression has duplicate parenthesis or not. But they provide a faulty algorithm as you have demonstrated with your input example (your Java code looks very similar to theirs).
Another algorithm
Here is another approach:
-
Use the stack to push the indices of where you have found opening parentheses. Don’t push anything else.
-
When encountering a closing parenthesis, read that index from the top of the stack, and then you have the two indices of the paired parentheses. Now it is a piece of cake to see if that pair is immediately wrapped by another pair of parentheses by just checking directly in the string at those “widened” indices.
Suggested code:
public static boolean isduplicate(String str){
Stack<Integer> s = new Stack<>(); // A stack of indices
int n = str.length();
for (int i = 0; i < n; i++) {
char curr = str.charAt(i);
if (curr == ')') {
int j = s.peek(); // Get index of matching '('
s.pop();
// If the pair is wrapped in another pair of parentheses:
if (j > 0 && str.charAt(j-1) == '(' && str.charAt(i+1) == ')') {
return true; // ...then we have a duplicated pair
}
} else {
s.push(i); // Push the index
}
}
return false;
}