Java 方案：冗余括号检测 O(N)

Source: Dev.to

问题

给定一个表示平衡表达式的字符串 s，判断其中是否包含 冗余括号。
如果同一子表达式被不必要或多余的括号包围，则该对括号是冗余的。

示例

• s = "((a+b))" → 冗余
• s = "(a+(b)/c)" → 不冗余
• s = "(a+b+(c+d))" → 不冗余

约束条件：1 ≤ |s| ≤ 10^5

朴素方法

1. 遍历字符串，找到左括号 (。
2. 向前扫描，定位匹配的右括号 )。
3. 提取它们之间的子串。
4. 检查子串是否包含运算符（+, -, *, /）。
   • 若没有运算符，则该括号是冗余的（例如 (a)）。
   • 若有运算符，则需要进一步检查，以避免把像 ((a+b)) 这样的嵌套冗余对计入。

该方法可能会多次扫描相同字符，在最坏情况下（深度嵌套的括号）导致 O(N²) 的时间复杂度。

使用栈的 O(N) 高效解法

表达式包含嵌套结构，天然适合 后进先出（LIFO） 的数据结构。通过顺序处理字符并使用栈，可以在一次遍历中检测冗余。

算法

1. 初始化一个空栈。
2. 逐个遍历字符串中的字符 ch：
   • 若 ch 是左括号 ( 或运算符（+, -, *, /），则将其压入栈。
   • 若 ch 是右括号 )：
     1. 弹出栈中元素，直到遇到左括号 ( 为止。
     2. 在弹出的过程中，检查是否出现过运算符。
        • 若 没有运算符，则当前这对括号是冗余的 → 返回 true。
     3. 丢弃匹配的 (。
3. 若遍历结束仍未检测到冗余，返回 false。

复杂度

• 时间： O(N) – 每个字符最多被压入和弹出一次。
• 空间： O(N) – 最坏情况下栈会保存表达式的所有字符。

参考实现（Java）

import java.util.Stack;

class Solution {
    public static boolean checkRedundancy(String s) {
        if (s == null || s.isEmpty()) {
            return false;
        }

        Stack stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            if (ch == ')') {
                boolean hasOperator = false;

                // Pop until the matching '('
                while (!stack.isEmpty() && stack.peek() != '(') {
                    char top = stack.pop();
                    if (isOperator(top)) {
                        hasOperator = true;
                    }
                }

                // Remove the '(' if present
                if (!stack.isEmpty()) {
                    stack.pop();
                }

                // No operator inside the parentheses → redundant
                if (!hasOperator) {
                    return true;
                }
            } else if (isOperator(ch) || ch == '(') {
                // Only push operators and '('; operands are irrelevant for redundancy check
                stack.push(ch);
            }
        }

        return false;
    }

    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }
}

checkRedundancy 方法在输入表达式包含任何冗余括号时返回 true，否则返回 false。