使用堆栈检查表达式是否包含重复括号中的表达式

Question

我要为以下内容编写一个函数：

给定一个平衡表达式，找出它是否包含重复的括号。如果相同的子表达式被多个括号包围，则一组括号是重复的。

例如，“((a+b)+((c+d)))”在“c+d”周围有重复的括号。

我的代码：

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。

根据我的代码逻辑，我期望它返回正确的结果。有什么错误吗？

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