Last Updated: 11 Dec, 2020
Redundant Brackets
Easy
Asked in companies
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.
Note :
A pair of brackets is said to be redundant when a subexpression is surrounded by needless/ useless brackets.
For Example :
((a+b)) has a pair of redundant brackets. The pair of brackets on the first and last index is needless.
While (a + (b*c)) does not have any pair of redundant brackets.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.
The first line of each test case contains a string denoting the expression.
Output Format :
For each test case, return “Yes” if the given expression contains at least one pair of redundant brackets, else return “No”.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
3 <= |S| <= 10^4
Time Limit: 1 sec
Approaches
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 :
- Define a stack, for keeping track of pairs of opening and closing brackets, let’s say ‘BRACKETS’.
- Iterate through the string and whenever we encounter an opening bracket or an operator( { ‘(’, ‘+’, ‘-’, ‘*’, ‘/’, } ) we will push the current character to the stack(‘BRACKETS’).
- Whenever we encounter ‘)’ in the string
- Now we will pop characters from the stack(‘BRACKETS’) until we pop an opening bracket { ‘(‘ } from the stack.
- If we find any operator ( { ‘+’, ‘-’, ‘*’, ‘/’ } ) before encountering ‘(’ then the current bracket is not redundant.
- If we do not find any operator, then the current bracket is redundant. Hence we will return true.
- If there is no redundant bracket, then return false.