Expression contains redundant bracket or not

Last Updated on October 10, 2022 by Gokul Kannan

Note: Expression may contain any of these ‘+‘, ‘*‘, ‘–‘, and ‘/‘ operators. Given expression is valid and there are no white spaces present.

Examples:

Input: “((a+b+c))”
Output: YES

Explanation:
((a+b+c)) can be reduced to (a+b+c) by removing outer redundant brackets ( (a+b+c) ).

Input: “(a+(b)/c)”
Output: YES

Explanation:
(a+(b)/c) can be reduced to (a+b/c) by removing outer redundant brackets of b i.e (a+ ( b ) /c).

Input: “((a+b) * c+z)”
Output: NO

Before going to the solution we need to understand the question by analysing the above examples. One thing is clear if ‘()’ contains operands only in that case these brackets are redundant. For example “((a+b)*c+z)” contains no redundant brackets because its inner and outer brackets contain operands and operators.

We will use the Stack data structure to solve this question. For any expression, if we are able to pick any sub-expression of this expression surrounded by (), then we are again left with ( ) as part of the string, which means it has no operands and operators between them so this is redundant brackets.

Algorithm:

1. Start iterating through the given expression and for each character in the expression

   • Start pushing every character of the string in the stack.
   • But, If the character is a close parenthesis ‘)’, then pop every character from the stack till matching open parenthesis i.e ‘(‘ is found.

2. Now for redundancy two conditions will arise while popping.

   • If immediate pop hits an open parenthesis ‘(‘, then we have found a duplicate parenthesis. For example, (((a+b))+c) has duplicate brackets around a+b. When we reach the second “)” after a+b, we have “((” in the stack. This means that is the redundant bracket.
   • If immediate pop doesn’t hit any operand with the operator (‘*’, ‘+’, ‘/’, ‘-‘) then it indicates the presence of unwanted brackets surrounded by expression. For instance, (a)+b contains unwanted () around a thus it is redundant.

Dry Run

Code Implementation

#include <bits/stdc++.h>
using namespace std;
 
// This function checks redundant brackets in a
// balanced expression
bool checkRedundantBracket(string& str){
    // create a stack of characters
    stack<char> character;
 
    // Iterate through the given expression
    for (auto& ch : str) {
 
        // if current character is close parenthesis ')'
        if (ch == ')') {
            char top = character.top();
            character.pop();
 
            // If immediate pop have open parenthesis '('
            // duplicate brackets found
            bool flag = true;
 
            while (!character.empty() and top != '(') {
 
                // Check for operators in expression
                if (top == '+' || top == '-' ||
                    top == '*' || top == '/')
                    flag = false;
 
                // Fetch top element of character
               // back
                top = character.top();
                character.pop();
            }
 
            // If operators not found
            if (flag == true)
                return true;
        }
 
        else
            character.push(ch); // push open parenthesis '(',
                  // operators and operands to stack
    }
    return false;
}
 

int main(){
    string str = "((a+b+c))";

    if(checkRedundantBracket(str)){
        cout<<"YES";
    }else{
        cout<<"NO";
    }

    return 0;
}

Output: YES

Time Complexity: O(N)
Space Complexity: O(N)

We tried to discuss whether the Expression contains redundant brackets or not. We hope this article gives you a better understanding of whether the Expression contains redundant brackets or not. PrepBytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program which will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.