Detecting Redundant Brackets in an Expression Using a Stack

Introduction

Parentheses play a crucial role in mathematical expressions by defining precedence and grouping operations. However, sometimes expressions contain unnecessary brackets that do not affect the result.

These unnecessary brackets are called redundant brackets.

Detecting redundant brackets is a popular stack-based interview problem because it tests a developer's understanding of:

In this article, we'll learn how to efficiently detect redundant brackets using a stack and implement the solution in Java.

Problem Statement

Given a balanced expression:

Code
s

determine whether it contains any redundant parentheses.

Return:

Code
true

if redundant brackets exist; otherwise:

Code
false

The expression may contain:

and lowercase variables.

What Are Redundant Brackets?

A pair of brackets is redundant if removing them does not change the meaning of the expression.

Example

Code
((a+b))

The outer brackets are unnecessary.

Can be reduced to:

Code
(a+b)

Therefore:

Code
Redundant = true

Example 1

Input

Code
((a+b))

Analysis

Outer brackets contain only:

Code
(a+b)

No operator exists directly inside the outer pair.

Therefore:

Code
true

Example 2

Input

Code
(a+(b)/c)

Analysis

Code
(b)

contains only a variable.

Removing brackets gives:

Code
a+b/c

which remains valid.

Thus:

Code
true

Example 3

Input

Code
(a+b+(c+d))

Analysis

The brackets around:

Code
(c+d)

are necessary because they group an actual sub-expression.

Therefore:

Code
false

Key Observation

Whenever we encounter a closing bracket:

Code
)

we should check what exists inside its matching opening bracket.

If there is no operator inside:

Code
+
-
*
/

then the brackets are redundant.

Stack-Based Approach

We use a stack to process the expression.

Rule

Push:

onto the stack.

Whenever we encounter:

Code
)

we inspect everything inside the matching pair.

Important Insight

Consider:

Code
(a)

Stack before processing ):

Code
(
a

Between the brackets:

Code
a

No operator exists.

Hence:

Code
Redundant

Another Example

Expression:

Code
(a+b)

Stack before ):

Code
(
a
+
b

Inside brackets:

Code
a+b

Contains operator:

Code
+

Therefore:

Code
Not Redundant

Algorithm

Traverse every character.

Case 1: Opening Bracket

Push:

Code
(

onto the stack.

Case 2: Operator

Push:

Code
+
-
*
/

onto the stack.

Case 3: Operand

Push the operand onto the stack.

Case 4: Closing Bracket

Initialize:

Code
hasOperator = false

Pop elements until:

Code
(

is found.

If any operator appears:

Code
hasOperator = true

After reaching:

Code
(

remove it.

If:

Code
hasOperator == false

then:

Code
return true

because the bracket pair is redundant.

Dry Run 1

Input

Code
((a+b))

Stack Processing

Push:

Code
(
(
a
+
b

Encounter first:

Code
)

Inside:

Code
a+b

Operator exists.

Not redundant.

Stack becomes:

Code
(

Encounter second:

Code
)

Inside:

Code
(nothing)

No operator.

Therefore:

Code
Redundant

Return:

Code
true

Dry Run 2

Input

Code
(a+(b)/c)

Processing:

Code
(
a
+
(
b
)

For:

Code
(b)

Inside brackets:

Code
b

No operator.

Thus:

Code
Redundant

Return:

Code
true

Dry Run 3

Input

Code
(a+b+(c+d))

First closing bracket:

Code
(c+d)

Contains:

Code
+

Not redundant.

Outer bracket also contains operators.

No redundant pair found.

Return:

Code
false

Java Solution

Java
class Solution {

    public static boolean checkRedundancy(String s) {

        Stack<Character> st = new Stack<>();

        for (char ch : s.toCharArray()) {

            if (ch == ')') {

                boolean hasOperator = false;

                while (!st.isEmpty() && st.peek() != '(') {

                    char top = st.pop();

                    if (top == '+' ||
                        top == '-' ||
                        top == '*' ||
                        top == '/') {

                        hasOperator = true;
                    }
                }

                // Remove matching '('
                if (!st.isEmpty()) {
                    st.pop();
                }

                // No operator inside => redundant
                if (!hasOperator) {
                    return true;
                }
            }
            else {
                st.push(ch);
            }
        }

        return false;
    }
}

Example Walkthrough

Input

Code
(a)

Stack:

Code
(
a

Encounter:

Code
)

Pop:

Code
a

Operator found?

Code
No

Therefore:

Code
true

Complexity Analysis

Let:

Code
n = length of expression

Time Complexity

Each character is:

Therefore:

Code
O(n)

Space Complexity

In the worst case:

Code
((((a+b))))

all characters are stored in the stack.

Therefore:

Code
O(n)

Why This Approach Works

For every pair of matching brackets:

Such brackets are unnecessary and therefore redundant.

The stack naturally helps us process nested expressions from the innermost level outward.

Edge Cases

Single Variable

Code
(a)

Output:

Code
true

Multiple Nested Brackets

Code
(((a+b)))

Output:

Code
true

Proper Expression

Code
(a+b+c)

Output:

Code
false

Nested Valid Expression

Code
(a+(b*c))

Output:

Code
false

because:

Code
(b*c)

contains an operator.

Conclusion

The "Expression Contains Redundant Bracket" problem is a classic stack application that demonstrates how matching parentheses can be analyzed efficiently.

The key idea is simple:

Whenever a closing bracket is encountered, check whether an operator exists inside the corresponding pair of brackets.

If no operator is present, the brackets are redundant.

Using a stack, we achieve:

Code
Time Complexity : O(n)
Space Complexity: O(n)

which perfectly satisfies the expected constraints for expressions containing up to 100,000 characters.