Table of Contents
Introduction
Problems related to mathematical expressions are found in abundance in almost every coding contest. Balanced parentheses, Infix, postfix, and prefix conversions are some of them.
One such problem is checking whether the given mathematical expression contains redundant parenthesis. A set of brackets that doesn’t add any value to the expression is known as Redundant Parentheses.
Problem Statement
Given valid mathematical expressions in the form of a string. You are supposed to return true if the given expression contains a pair of redundant brackets, else return false. The given string only contains ‘(‘, ’)’, ‘+’, ‘-’, ‘*’, ‘/’ and lowercase English letters.
For example: In the expression, ((a+b)) – (b), the a+b part is enclosed in two sets of brackets. Removing one of them will not make any difference in the expression. Also, just after the – operator, b is enclosed inside a bracket, which is unnecessary.
This creates redundancy which leads to unnecessary work. In this article, we’ll be looking into this problem and finding a way to solve it. So, let’s get started!
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 Codestudio.
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 CodeStudio. Without further ado, have it accepted as early as possible.
Frequently Asked Questions
Redundant parentheses are unnecessary brackets stuffed inside a mathematical expression.
Stack is used for checking if an expression contains redundant parenthesis.
You can submit your code on CodeStudio and get it accepted right away.
Yes, CodeStudio 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.
Key Takeaways
As mentioned earlier, questions related to parentheses and mathematical expressions are prevalent.
These questions are asked during various coding contests as well as placements tests.
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, Codestudio 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!
By: Vaishnavi Pandey
