Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# 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.

### 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 (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.