Solution Approach
Since a bracket consists of a left and right pair, we need a special data structure. The idea is to use the stack to keep track of the opening and closing brackets. If we remove any subexpression from the given string which is enclosed by “()” and after that, if there exist any pair of opening and closing brackets“()” which does not have any operator(‘+’,’-’,’*’,’/’) in between them, then the expression will have a redundant pair of brackets.
The steps are as follows :
1. Define a stack for keeping track of pairs of opening and closing brackets, let’s say ‘st’. 2. Iterate through the string, and whenever we encounter an opening bracket or an operator like( { ‘(’, ‘+’, ‘-’, ‘*’, ‘/’, } ) we will push the current character to the stack(‘st’). 3. Whenever we encounter ‘)’ in the string (i) Now we will pop characters from the stack(‘st’) until we pop an opening bracket { ‘(‘ } from the stack. (ii) If we find any operator ( { ‘+’, ‘-’, ‘*’, ‘/’ } ) before encountering ‘(’ then the current bracket is not redundant. (iii) If we do not find any operator, then the current bracket is redundant. Hence we will return true. 4. If there is no redundant bracket, then return false.
Before directly jumping to the solution, we suggest you try and solve this problem on Coding Ninjas Studio.
Implementation
Let’s see the implementation of the above approach.
#include <bits/stdc++.h>
using namespace std;
//function to check redundant parentheses
bool checkRedundantBrackets(string s)
{
// create a stack
stack<char> st;
bool answer = false;
// Iterate through the given expression
for (int i = 0; i<s.length(); i++) {
// if current character is an operand
if (s[i] == '+' || s[i] == '-' ||s[i] == '*' || s[i] == '/')
{
st.push(s[i]);
}
// if current character is left bracket
else if(s[i] == '(')
{
st.push(s[i]);
}
// if current character is right bracket
else if(s[i] == ')')
{
if(st.top() == '(')
{
answer = true;
}
while (st.top() == '+' || st.top() == '-' ||st.top() == '*' || st.top() == '/')
{
st.pop();
}
// pop to remove the corresponding opening bracket
st.pop();
}
}
return answer;
}
int main()
{
int test;
cin>>test;
while(test--)
{
string s;
cin>>s;
bool answer;
answer = checkRedundantBrackets(s);
if(answer)
cout<<"Redundant brackets are present!!";
else
cout<<"Redundant brackets are not present!!";
}
return 0;
}
Output
4
((a+b))-(b)
Redundant brackets are present!!
(a+(b)/c)
Redundant brackets are present!!
(a+b*(c/d)
Redundant brackets are not present!!
((a-b)*(b-c))
Redundant brackets are not present!!
Time Complexity
O(|S|), where |S| is the length of the given string.
Reason: We are iterating through the given string which will take O(|S|) time. Also, we are performing push and pop operations on a stack which take constant time. Thus, the total time complexity is O(|S|).
Space Complexity
O(|S|), where |S| is the length of the given string.
Reason: We are using a stack for keeping track of brackets, in the worst case when there are no brackets and all the characters in the string are either operators or operands the size of the stack will become |S|. Thus, the overall space complexity will be O(|S|).
If you’ve made it this far, congratulations, Champ. The problem of “Redundant Parentheses” is now resolved. If you haven’t already submitted it to Coding Ninjas Studio. Without further ado, have it accepted as early as possible.
Check out this article - Balanced Parentheses
Frequently Asked Questions
What are redundant parentheses?
Redundant parentheses are unnecessary brackets stuffed inside a mathematical expression.
Which data structure is used to find if an expression contains redundant parentheses?
A stack is used for checking if an expression contains redundant parenthesis.
Where can I submit my “Redundant Parentheses” code?
You can submit your code on Coding Ninjas Studio and get it accepted right away.
Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?
Yes, Coding Ninjas Studio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.
Conclusion
As mentioned earlier, questions related to parentheses and mathematical expressions are prevalent.
We discussed one such problem, “Redundant Parentheses” along with its approach and implementation in C++, in this article.
Other key problems are Valid Parentheses and Balanced Parentheses, which are similar to Redundant Parentheses. Don’t forget to try them out because it is a rigorous practice that allows us to hone our skills.
To practice more such problems, Coding Ninjas Studio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.
Keep Practising!
38+ registered 
