Home » Interview coding problems/challenges

Redundant Bracket

Redundant Bracket: Here, we are going to learn to check if an expression contains the redundant parentheses or not? The problem has been featured in interview rounds of companies such as Flipkart, Amazon, Snapdeal, Microsoft, etc. Submitted by Divyansh Jaipuriyar, on May 05, 2020

Problem statement

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.

Solution Approach

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