As a programmer, redundancy of any kind is a big NO!
The same goes for braces. Redundant braces in an expression only add more computational steps and make the expression look unoptimized.
So, when we are asked to check if the given expression has a redundant bracket or not, it checks the presence of multiple brackets. Also, removing unnecessary braces will not have any effect on the output of the expression.
The redundant braces problem is one of the advanced problems asked in many interviews. This includes other multiple algorithms and basics of programming which makes it one of the top asked questions.
Other questions include the longest common prefix, subsequence, substring, reverse of an array, and more.
In this post, we are going to discuss in detail what are redundant braces and how you can check if the given expression contains unnecessary braces or not.
Problem Statement:
You are given a string of balanced expressions. You need to find if the string contains any redundant braces or not. It is said that a pair of parentheses is redundant if the exact sub-expression consists of multiple and unnecessary braces.
So, you need to print “Yes” if any redundant braces are there. Otherwise, print “No”.
Note that the expression will also have some operators. The given string is valid and contains no white spaces.
Let’s understand the problem statement with an example.
Consider the following strings:
- S1: (a+b)
- S2: ((a+b))
- S3: ((a) +b/ c)
The output of these given strings will be:
- No
- Yes
- Yes
Here’s an explanation:
- For S1: (a+b), the string does not contain any redundant braces. Therefore, the output will print “No”.
- For S2: ((a+b)), this string can be written as (a+b), and removing the braces will have no effect. Therefore, the output displayed Yes which means that there are redundant braces.
- Lastly, for S3: ((a) +b/c), this string can be written as (a+b/c), and removing the extra braces will have no effect on the output. Therefore, the output displayed Yes which means that there are redundant braces.
How To Resolve Redundant Braces Problem
To find and resolve redundant braces in programming, the stack-based approach is followed. In this approach, we check for all the sub-expressions. If any sub-expression is already surrounded by () and we are again left with (), this means that redundant braces are found in the string.
In the stack approach, with each iteration, the characters of the string are iterated. In case a character in any iteration is an open parenthesis or operator, the character is pushed into the stack.
Otherwise, if the character found is a close parenthesis, the character is popped out from the stack. This continues till the opening parenthesis is not found to complement the closing one.
Now, when it comes to redundant braces, two situations may occur. They are:
- In case there is an immediate pop for the open parenthesis, then, it means there are duplicate parentheses. For example: consider an expression: ((a+b)) +c). In this expression, when the first closing parenthesis will be encountered, there will be two (( opening parenthesis left. Now, that the opening of the stack is an opening parenthesis, it means that there are redundant parentheses.
- The next scenario can be when there is no immediate hit from the parentheses around the operators, which means that there are unnecessary parentheses around the operator. For instance, consider the expression (a+b). In this, the braces surrounding a and b are unnecessary. This means that there are redundant braces.
Another Approach To Check Redundant Braces
Other than using Stack, one more approach can be used to check redundant brackets. In this approach, the number of symbols/ operators is counted. Also, it counts the total number of parenthesis present in the expression.
In this approach, if the number of symbols is not equal to the number of parentheses, the function will return False.
Algorithm To Find Redundant Braces
Now, here we have mentioned the complete algorithm that you will have to use to find redundant braces in the given expression. While writing the code, make sure to follow the algorithm to get desired output.
- To begin with, initialize the String S which you need to check.
- Initialize a stack data structure as well.
- Check through the whole string if the next character or index is equal to “)”. If yes, push the traversed character into the stack.
- Else, you will have to create a new variable “Top” of the character type and then store the element to it. You will then have to pop the top.
- Now, a Boolean type variable needs to be initialized. Name it Flag and initialize it TRUE.
- Check the string while the top is not “(“. If the top is equal to any operator, change the value of Flag to False.
- Store the current variable at the top of the stack and then pop the top.
- Recheck if the value of Flag is True. if yes, return True.
- Else return False.
- If the expression’s return value is True, return Yes. Otherwise, return No.
Complexity Analysis
- Time complexity: The time complexity of this algorithm is O(n). Here, n represents the number of characters.
- Space Complexity: The Space complexity for this algorithm is O(n). It represents the space used to store n characters.
The longest common prefix of an array
The longest common prefix of an array or of a couple of strings is the longest string which is the prefix in both the strings.
For instance, let us assume that there are A1 and A2 strings. The longest common prefix between these two pairs of arrays will be A.
That, as we can see here, is the common prefix of both the strings. We can better explain this problem by taking into consideration an example question related to this problem:
- You have been given an array “ARR” which consists of an “N” number of strings. You are being asked to find out the longest common prefix of this array. In case you figure out that there is no prefix, you can return an empty array.
- First, we shall discuss some of the approaches that you can try while solving the given problem.
Approach:
Let us assume that in a given array there are strings known as “coding”, “codingninja”, ” codezon”, and “coders”. Now, as per the first approach, you can try and figure out the alphabets that are matching in the first half of the strings.
Here we can clearly see that the alphabets “cod” are common for all the strings. Hence, that becomes the longest common prefix of the example.
Logic:
//for traversing all characters of first String
for(int i=0; i<arr[0].length() ; i++) {
char ch = arr[0] [i];
bool match = true;
//for comparing ch with rest os the strings
for(int j=1; j<n; j++) {
//not match
if(arr[j].size() < i || ch != arr[j] [i]) {
match = false;
break;
}
}
if(match == false)
break;
else
ans.push_back(ch) ;
}
return ans;
}
This is the easiest approach that you can go by for solving problems of this sort. Keep in mind that the longest common prefix can be considered till the last common digit or alphabet in a given string.
Conclusion
Any expression having redundant braces only increases the time taken to resolve a particular expression as it will only add additional computational steps to the whole process. Therefore, it is necessary to make sure to remove any extra and unwanted brackets from the expression.
This is one of the ways to make your expression optimized. How optimize your code is, defines the type of programmer you are. Therefore, to check the same, in most technical interviews, it is asked to remove redundant braces from an expression.
Therefore, if you have any interview impending or you are preparing for an interview, do not skip this problem. Make sure you go through the complete guide to understand the problem and learn to fix the same.
Also Read – Security Issues and Challenges in IoT development
