Q:

# Redundant Bracket

Given a string of balanced expression, find if it contains a redundant parenthesis or not. A set of parentheses is redundant if the same sub-expression is surrounded by unnecessary or multiple brackets. Print "Yes" if redundant else "No".

Input:

The first line of input contains an integer T denoting the number of test cases. The next line T contains an expression. The expression contains all characters and ^, *, /, +, -.

Output:

For each test case, in a new line, print YES or NO if the expression is redundant or not.

Examples:

```    Input:
T = 1
((a+b))

Output:
YES
(a+b) is surrounded by extra (), which is of no need.

Input:
T = 1
(a+(a+b))

Output:
NO
here there is no extra bracket.```

Stack Approach

We will traverse from left to right and perform the following operations.

• If the given character is not ')' then push that into stack otherwise we check for other probabilities as:
• We start to pop elements from the stack and check if the immediately popped element is '(' without any other any operator (+, -, /, *) in between them then it is a possible case of redundant brackets:
• If the immediately popped element is open bracket ')' then it is a condition of the redundant bracket.

Example:

```    ((a)),(((a+b))),((c)+d)
```

Pseudo Code:

```string Redundant(string str)
{
stack<char>st     //declare stack
//iterate from left to right
for(int i=0;i<str.length();i++)
{
//is character is not ')' then push it into the stack.
if(str[i]!=')')
{
st.push(str[i])
}
//if the character is '(' the check for above
//mentioned possibilites
else if(str[i]==')')
{
//declare a boolean variable to check for
//immediate popped element condition.
bool flag=true

//variable to store temporary top elements.
int x=st.top()
st.pop()
while(x!='(')
{
// Check for operators in expression
if(str[i]=='+'||str[i]=='-'||str[i]=='/||str[i]=='^'||str[i]=='*')
flag=false
x=st.top()
st.pop()
}
//if there is immediate bracket without any
//operator then its redundant bracket.
if(flag==true)
{return "YES"}
}
}
//there is no redundant brackets.
return "NO"
}
```

Time Complexity for above approach is: O(n)
Space Complexity for above approach is: O(n)

C++ Implementation:

``````#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
ll t;
cout << "Enter number of test cases: ";
cin >> t;

while (t--) {
string str;
cout << "Enter string: ";
cin >> str;

stack<char> st;

for (int i = 0; i < str.length(); i++) {
//is character is not ')' then push it into the stack.
if (str[i] != ')')
st.push(str[i]);
//if the character is '(' the check for
//above mentioned possibilites
else {
//declare a boolean variable to check for
//immediate popped element condition.
bool flag = true;
char x = st.top(); //variable to store temporary top elements.
st.pop();
while (x != '(') {
// Check for operators in expression
if (x == '+' || x == '-' || x == '*' || x == '^' || x == '/')
flag = false;
x = st.top();
st.pop();
}
//if there is immediate bracket without any operator
//then its redundant bracket.
if (flag == true) {
cout << "YES"
<< "\n";
goto end;
}
}
}
cout << "NO"
<< "\n";
end:;
}
return 0;
}
``````

Output

```Enter number of test cases: 4
Enter string: (a+b)
NO
Enter string: ((a+b))
YES
Enter string: (a+(b*c)-(d+e))
NO
Enter string: (a)
YES
```

2) Implementation

Instead of using the stack to check redundancy, we make two variables to check the number of operators and the number of brackets and check for the condition if some character is present without any operators.

Pseudo Code:

```string Redundant(string str)
{
//declare two variable for bracket and
//operator respectively.
int x,y
x=0  //initialise them with 0
y=0

//iterate through loop
for(int i=0;i<str.length();i++)
{
//if there is immediate breacket return yes
if(str[i]=='(' and str[i+2]==')')
return "YES"
//count number of '('
if(str[i]=='(')
x++;
//count number of operators.
if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='^')
y++;
}

//if number of breacket is higher than operator
//then its redundant else its not redundant.
if(x>y)
return "YES"
else
return "NO"
}
```

C++ Implementation:

``````#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
ll t;
cout << "Enter number of test cases: ";
cin >> t;

while (t--) {
string str;
cout << "Enter string: ";
cin >> str;

int x = 0;
int y = 0;

for (int i = 0; i < str.length(); i++) {
//immediate bracket without any operators
if (str[i] == '(' and str[i + 2] == ')') {
cout << "YES"
<< "\n";
goto end;
}
else if (str[i] == '(')
x++;
if (str[i] == '+' || str[i] == '-' || str[i] == '^' || str[i] == '*' || str[i] == '/')
y++;
}
//if number of brackets is greater than its redundant.
if (x > y)
cout << "YES"
<< "\n";
else
cout << "NO"
<< "\n";
end:;
}
return 0;
}
``````

Output

```Enter number of test cases: 3
Enter string: (a)
YES
Enter string: (a+(b-c))
NO
Enter string: (a+(b*c)-d+c)
NO```