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".
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 ^, *, /, +, -.
For each test case, in a new line, print YES or NO if the expression is redundant or not.
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.
We will traverse from left to right and perform the following operations.
Time Complexity for above approach is: O(n)
Space Complexity for above approach is: O(n)
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.
Outputneed an explanation for this answer? contact us directly to get an explanation for this answer