Expression Contains Redundant Bracket or Not

Given a string s containing an expression of operators, operands, and parenthesis. Find if the given string contains any unnecessary parenthesis without which the expression will still give the same result. In other words, we have to find that expression contains a redundant bracket or not.

Redundant Bracket

If an expression or sub-expression is surrounded by unnecessary or multiple brackets without which the expression will still give the same result, such brackets are known as redundant brackets.

For instance :

Let string s = “(a+(b)/c)”.

Here, the given string can be written as (a+b/c) and will still represent the same meaning. Therefore, we can say that the given string s = “(a+(b)/c)” contains redundant brackets.

Example

Input : s = “((a+b))”

Output : Yes

Input : s = “(a+b*(c-d))”

Output : No

Algorithm for finding Expression Contains Redundant Bracket or Not

1. Initialize a string s containing an expression of operators, operands, and parenthesis.
2. Create a stack data structure.
3. Traverse through the given string and check if the character at the current index of the string is not equal to ‘)’, push the character at the current index of the string in the stack.
4. Else create a variable top of character type and store the element at the top of the stack in it and pop the top of the stack.
5. Create a variable flag of boolean type and initialize it as true.
6. Traverse while the variable top is not equal to ‘(‘ and check if the variable top is equal to either ‘+’, ‘-‘, ‘*’ or ‘/’, update the value of the boolean variable flag as false.
7. Store the element at the top of the stack in the variable top and pop the top of the stack.
8. Check if the value of the boolean variable flag is equal to true, return true.
9. Return false.
10. If the returned value is equal to true, print “Yes” else print “No”.

C++ Program for finding Expression Contains Redundant Bracket or Not

#include <bits/stdc++.h> 
using namespace std; 
  
bool checkRedundancy(string& s){ 
    stack<char> st; 
  
    for(auto& ch : s){ 
        if(ch == ')'){ 
            char top = st.top(); 
            st.pop(); 
  
            bool flag = true; 
  
            while(top != '('){ 
                if(top == '+' || top == '-' || top == '*' || top == '/'){ 
                    flag = false; 
                }
  
                top = st.top(); 
                st.pop(); 
            } 
  
            if(flag == true){ 
                return true; 
            }
        } 
        else{
            st.push(ch); 
        }
    } 
    return false; 
} 
  
void findRedundant(string& s){ 
    bool ans = checkRedundancy(s); 
    if(ans == true){ 
        cout << "Yes\n";
    }
    else{
        cout << "No\n"; 
    }
} 
  
int main(){
    
    string s = "((a+b))"; 
    findRedundant(s); 
  
    return 0; 
}

Yes

Java Program for finding Expression Contains Redundant Bracket or Not

import java.util.Stack;

class RedundantBrackets{ 

    static boolean checkRedundancy(String s){ 
        Stack<Character> st = new Stack<>(); 
        
        char[] str = s.toCharArray(); 
        
        for(char ch : str){ 
            if(ch == ')'){ 
                char top = st.peek(); 
                st.pop(); 
  
                boolean flag = true; 
  
                while(top != '('){ 
                    if(top == '+' || top == '-' || top == '*' || top == '/'){ 
                        flag = false; 
                    } 
    
                    top = st.peek(); 
                    st.pop(); 
                } 
                
                if(flag == true){ 
                    return true; 
                } 
            } 
            
            else{ 
                st.push(ch); 
            }                
        } 
        return false; 
    } 
  
    static void findRedundant(String str){ 
        boolean ans = checkRedundancy(str); 

        if(ans == true){ 
            System.out.println("Yes"); 
        } 
        
        else{ 
            System.out.println("No"); 
        } 
    } 
    
    public static void main(String[] args){ 
        
        String str = "((a+b))"; 
        findRedundant(str); 
  
    } 
}

Yes

Complexity Analysis

Time Complexity: O(n) where n is the number of the characters in the given expression.

Space Complexity: O(n) because we used space for n characters.

References