在java中使用堆栈查找字符串中的重复括号

Question

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));
    }
}

输入--->“((a+b)(+)(c+d))” 输出应该为 false，但它返回 true。我知道从数学上来说，只将操作数（+）放在括号中是错误的，但根据我的代码的逻辑，它应该返回 false

Answer 1

您的代码在执行 return true 之前不会检查是否有两个连续的

右括号。其次，检查从堆栈中弹出的非左括号的计数是否为零并不能充分表明有两个连续的左括号与最后两个右括号相关。

我的猜测是您通过阅读 GeeksforGeeks 文章

查找表达式是否有重复的括号得到了这个算法。但他们提供了一个错误的算法，正如您在输入示例中所演示的那样（您的 Java 代码看起来与他们的非常相似）。

另一种算法

这是另一种方法：

• 使用堆栈压入您找到左括号的位置的

  索引。不要推任何其他东西。

• 遇到右括号时，从堆栈顶部读取该索引，然后就得到了配对括号的两个索引。现在，只需直接检查那些“加宽”索引处的字符串，即可轻松查看该对是否立即被另一对括号括起来。

建议代码：

    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;
    }