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:
Stack data structures
Expression parsing
Parentheses matching
Operator precedence
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:
s
determine whether it contains any redundant parentheses.
Return:
true
if redundant brackets exist; otherwise:
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
((a+b))
The outer brackets are unnecessary.
Can be reduced to:
(a+b)
Therefore:
Redundant = true
Example 1
Input
((a+b))
Analysis
Outer brackets contain only:
(a+b)
No operator exists directly inside the outer pair.
Therefore:
true
Example 2
Input
(a+(b)/c)
Analysis
(b)
contains only a variable.
Removing brackets gives:
a+b/c
which remains valid.
Thus:
true
Example 3
Input
(a+b+(c+d))
Analysis
The brackets around:
(c+d)
are necessary because they group an actual sub-expression.
Therefore:
false
Key Observation
Whenever we encounter a closing bracket:
)
we should check what exists inside its matching opening bracket.
If there is no operator inside:
+
-
*
/
then the brackets are redundant.
Stack-Based Approach
We use a stack to process the expression.
Rule
Push:
onto the stack.
Whenever we encounter:
)
we inspect everything inside the matching pair.
Important Insight
Consider:
(a)
Stack before processing ):
(
a
Between the brackets:
a
No operator exists.
Hence:
Redundant
Another Example
Expression:
(a+b)
Stack before ):
(
a
+
b
Inside brackets:
a+b
Contains operator:
+
Therefore:
Not Redundant
Algorithm
Traverse every character.
Case 1: Opening Bracket
Push:
(
onto the stack.
Case 2: Operator
Push:
+
-
*
/
onto the stack.
Case 3: Operand
Push the operand onto the stack.
Case 4: Closing Bracket
Initialize:
hasOperator = false
Pop elements until:
(
is found.
If any operator appears:
hasOperator = true
After reaching:
(
remove it.
If:
hasOperator == false
then:
return true
because the bracket pair is redundant.
Dry Run 1
Input
((a+b))
Stack Processing
Push:
(
(
a
+
b
Encounter first:
)
Inside:
a+b
Operator exists.
Not redundant.
Stack becomes:
(
Encounter second:
)
Inside:
(nothing)
No operator.
Therefore:
Redundant
Return:
true
Dry Run 2
Input
(a+(b)/c)
Processing:
(
a
+
(
b
)
For:
(b)
Inside brackets:
b
No operator.
Thus:
Redundant
Return:
true
Dry Run 3
Input
(a+b+(c+d))
First closing bracket:
(c+d)
Contains:
+
Not redundant.
Outer bracket also contains operators.
No redundant pair found.
Return:
false
Java Solution
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
(a)
Stack:
(
a
Encounter:
)
Pop:
a
Operator found?
No
Therefore:
true
Complexity Analysis
Let:
n = length of expression
Time Complexity
Each character is:
Therefore:
O(n)
Space Complexity
In the worst case:
((((a+b))))
all characters are stored in the stack.
Therefore:
O(n)
Why This Approach Works
For every pair of matching brackets:
If at least one operator exists inside, the brackets contribute to expression grouping.
If no operator exists inside, the brackets wrap a single operand or another already-grouped expression.
Such brackets are unnecessary and therefore redundant.
The stack naturally helps us process nested expressions from the innermost level outward.
Edge Cases
Single Variable
(a)
Output:
true
Multiple Nested Brackets
(((a+b)))
Output:
true
Proper Expression
(a+b+c)
Output:
false
Nested Valid Expression
(a+(b*c))
Output:
false
because:
(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:
Time Complexity : O(n)
Space Complexity: O(n)
which perfectly satisfies the expected constraints for expressions containing up to 100,000 characters.