Check Redundant Brackets

Try it on GfG Practice

Given a balanced expression string s, check if it contains redundant parentheses. Return true if redundant, else false.
Redundant Parentheses: Parentheses are redundant if removing them does not change the expression.
Note: Expression is valid, contains operators +, -, *, /, and no spaces.

Examples: 

Input: s = "((a+b))"
Output: true
Explanation: ((a+b)) can be simplified to (a+b), which means the outer parentheses are redundant.

Input: s = "(a+(b)/c)"
Output: true
Explanation: (a+(b)/c) can reduced to (a+b/c) because b is surrounded by () which is redundant.

Input: s = "((a+b)*c)"
Output: false
Explanation: Removing any parentheses would change the order of evaluation, so none of them are redundant.

[Approach] Using Stack - O(n) Time and O(n) Space

Redundant parentheses occur in two cases:

1. Extra around an expression → ((a+b)) - The outermost brackets are unnecessary.
2. Around a single element → (a)+b - The parentheses around 'a' are not needed.

The idea is to use a stack so that whenever we encounter a closing parenthesis ')', we can check the element before it. For every such pair, if no operator (+, -, *, /) exists within, then the parentheses are redundant.

Steps to Implement the Approach:

1. Traverse each character of the expression.
2. If the character is an opening parenthesis '(', an operand (a–z), or an operator (+, -, *, /), push it onto the stack.
3. If the character is a closing parenthesis ')':
   => Pop elements from the stack until an opening parenthesis '(' is found.
   => While popping, check if at least one operator (+, -, *, /) exists.
   => If no operator is found (i.e., the parentheses enclose only a single operand or nothing), the parentheses are redundant.
   => If the very first element popped is '(', this also indicates redundancy.
4. If redundancy is detected, return true.
5. If the entire expression is scanned without finding redundancy, return false.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

bool checkRedundancy(string& s){
    stack<char> st;

    // Iterate through the given expression
    for (int i=0; i<s.size(); i++) {

        // if current character is close parenthesis ')'
        if (s[i] == ')') {
            char top = st.top();
            st.pop();

            // If immediate pop have open parenthesis '('
            // duplicate brackets found
            bool flag = true;
            
            while (!st.empty() and top != '(') {

                // Check for operators in expression
                if (top == '+' or top == '-' or
                    top == '*' or top == '/')
                    flag = false;

                // Fetch top element of stack
                top = st.top();
                st.pop();
            }

            // If operators not found
            if (flag == true)
                return true;
        }
        else
            st.push(s[i]); 
    }
    return false;
}

int main()
{
    string s = "((a+b))";
    cout<<(checkRedundancy(s)?"true":"false");
    return 0;
}

import java.util.Stack;

public class GFG {
    static boolean checkRedundancy(String s) {
        
        Stack<Character> st = new Stack<>();
        char[] str = s.toCharArray();
        
        // Iterate through the given expression 
        for (int i=0; i<s.length(); i++) {
              char ch = str[i];
            // if current character is close parenthesis ')' 
            
            if (ch == ')') {
                char top = st.peek();
                st.pop();

                // If immediate pop has open parenthesis '(' 
                // duplicate brackets found 
                boolean flag = true;

                while (top != '(') {

                    // Check for operators in expression 
                    if (top == '+' || top == '-'
                            || top == '*' || top == '/') {
                        flag = false;
                    }

                    // Fetch top element of stack 
                    top = st.peek();
                    st.pop();
                }

                // If operators not found 
                if (flag) {
                    return true;
                }
            } else {
                st.push(ch); 
            }              
        }
        return false;
    }
    public static void main(String[] args) {
        String s = "((a+b))";
        System.out.println(checkRedundancy(s)?"true":"false");
    }
}

def checkRedundancy(s):
    st = [] 
    n = len(s)

    # Iterate through the given expression 
    for i in range(n):
        ch = s[i]

        # If current character is closing parenthesis ')'
        if ch == ')': 
            top = st[-1] 
            st.pop() 

            # Assume redundant unless operator found
            flag = True

            while top != '(': 
                # Check for operators in expression 
                if top in {'+', '-', '*', '/'}: 
                    flag = False

                # Fetch top element of stack 
                top = st[-1] 
                st.pop()

            # If no operator found → redundant
            if flag:
                return True
        else:
            st.append(ch) 
    return False


if __name__ == '__main__':
    s = "((a+b))"
    print("true" if checkRedundancy(s) else "false")

using System; 
using System.Collections.Generic;

class GFG{
  static bool checkRedundancy(String s) {
      
        Stack<char> st = new Stack<char>();
        char[] str = s.ToCharArray();
        
        // Iterate through the given expression 
        foreach (char ch in str){

            // if current character is close parenthesis ')' 
            if (ch == ')'){
                char top = st.Peek();
                st.Pop();

                // If immediate pop has open parenthesis '(' 
                // duplicate brackets found 
                bool flag = true;

                while (top != '('){

                    // Check for operators in expression 
                    if (top == '+' || top == '-'
                            || top == '*' || top == '/'){
                        flag = false;
                    }

                    // Fetch top element of stack 
                    top = st.Peek();
                    st.Pop();
                }

                // If operators not found 
                if (flag == true){
                    return true;
                }
            } 
            else{
                st.Push(ch); 
            }        
        }
        return false;
    }

    public static void Main(String[] args){
        String s = "((a+b))";
        Console.WriteLine(checkRedundancy(s)?"true":"false");
    }
}

function checkRedundancy(s){
    
    var st = [];
    var res = false;
    
    // Iterate through the given expression
    s.split('').forEach(ch => {
        
        // if current character is close parenthesis ')'
        if (ch == ')') {
            var top = st[st.length-1];
            st.pop();

            // If immediate pop has open parenthesis '('
            // duplicate brackets found
            var flag = true;

            while (st.length!=0 && top != '(') {

                // Check for operators in expression
                if (top == '+' || top == '-' || 
                    top == '*' || top == '/')
                    flag = false;

                // Fetch top element of stack
                top = st[st.length-1];
                st.pop();
            }

            // If operators not found
            if (flag == true)
                res = true;
        }

        else
            st.push(ch); 
    });
    return res;
}

// Driver code
var s = "((a+b))";
console.log(checkRedundancy(s)?"true":"false");

true