Detect Redundant Parentheses Using a Stack

Parentheses are redundant if removing them doesn’t change the expression’s meaning. For example, ((a+b)) has redundant outer parentheses, and (a) wraps a single operand unnecessarily.

Examples

Expression	Redundant?	Why
(a+b)	No	Parentheses group an operation
((a+b))	Yes	Outer pair is unnecessary
(a)	Yes	Single operand needs no grouping
a+(b*c)	No	Controls precedence
a+((b*c))	Yes	Inner pair suffices

The Algorithm

Push characters onto the stack. When you encounter ), pop until you find (. If you popped no operators between the parentheses, they are redundant.

def has_redundant_parentheses(expression):
    """
    Detect redundant parentheses in an expression.
    Time: O(n), Space: O(n)
    """
    stack = []
    operators = {'+', '-', '*', '/'}

    for char in expression:
        if char == ')':
            has_operator = False

            while stack and stack[-1] != '(':
                top = stack.pop()
                if top in operators:
                    has_operator = True

            stack.pop()  # Remove the '('

            if not has_operator:
                return True
        else:
            stack.append(char)

    return False

Trace

Expression: ((a+b))

char | stack              | action
-----|--------------------|---------
(    | [(]                | push
(    | [(, (]             | push
a    | [(, (, a]          | push
+    | [(, (, a, +]       | push
b    | [(, (, a, +, b]    | push
)    | [(, (]             | pop b,+,a → found operator ✓
)    | []                 | pop ( → NO operator ✗ → REDUNDANT!

Expression: (a+b)

char | stack          | action
-----|----------------|---------
(    | [(]            | push
a    | [(, a]         | push
+    | [(, a, +]      | push
b    | [(, a, +, b]   | push
)    | []             | pop b,+,a → found operator ✓ → OK

Count All Redundant Pairs

To count how many redundant pairs exist:

def count_redundant_parentheses(expression):
    """Count the number of redundant parenthesis pairs."""
    stack = []
    operators = {'+', '-', '*', '/'}
    count = 0

    for char in expression:
        if char == ')':
            has_operator = False
            while stack and stack[-1] != '(':
                if stack.pop() in operators:
                    has_operator = True
            stack.pop()
            if not has_operator:
                count += 1
        else:
            stack.append(char)

    return count

Edge Cases

• Empty expression — returns False
• No parentheses — returns False (nothing to be redundant)
• (((a))) — two redundant pairs detected
• Unary operators — (-a) depends on interpretation; typically considered not redundant
• Spaces in expression — filter them out before processing

When to Use This Pattern

• Expression parsers and compilers that simplify or lint code
• Code formatters that remove unnecessary grouping
• Interview problems involving parenthesis validation

Related Problems

• Valid Parentheses (LeetCode 20) — check if balanced
• Minimum Remove to Make Valid Parentheses (LeetCode 1249)
• Remove Outermost Parentheses (LeetCode 1021)
• Score of Parentheses (LeetCode 856)