Expression contains redundant bracket or not

Time: O(n)

Space: O(n)

Intuition

Check if expression has redundant brackets like ((a+b)). Stack-based: if operator found before closing bracket, brackets are non-redundant.

Algorithm

1Push everything except ")". On ")": pop until "(". If top after "(" pop has no operator: redundant.

Common Pitfalls

•Redundant bracket: closing bracket pops "()" with no operator between them. Track operator presence between brackets.

Expression contains redundant bracket or not.java

Java

// Approach: Stack-based. If after popping an operator inside brackets nothing useful remains, it's redundant.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public static boolean checkRedundancy(String s) {
        Stack<Character> st = new Stack<>();

        for (char ch : s.toCharArray()) {
            if (ch == ')') {
                int opCnt = 0;
                while (!st.isEmpty()) {
                    char popped = st.pop();
                    if (popped == '(')
                        break;
                    else if (isOperator(popped))
                        opCnt++;
                }
                
                if (opCnt == 0)
                    return true;
            } else
                st.push(ch);
        }

        return false;
    }

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

Was this solution helpful?