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 subexpression 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:

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.

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, indepth subject knowledge for better understanding.