Last Updated: 17 Feb, 2021
Ninja And A Complex Expression
Moderate
Asked in company
Ninja has been given a string ‘STR’ of a balanced expression containing '(',')', operators (+, -, /, *), and English lower case alphabets. ‘STR’ may be complex in nature if it contains unnecessary multiple brackets. His task is to check whether ‘STR’ can be converted to a simplified string or not. A simplified string is one in which there are no unnecessary multiple brackets.
Here are some examples of complex ‘STR’ with multiple unnecessary brackets “((a+b))”,“((a+(b)) * (c/d))” and “(((a+b))+((c * d)))”. These can be simplified by removing unnecessary multiple brackets such as “(a+b)”,“((a+b) * (c/d))” and “((a+b)+(c * d))”.
As Ninja is busy with some other task so he asks you for help.
Can you help Ninja to check whether the given string ‘STR’ can be simplified or not?
Input Format :
The first line of input contains an integer ‘T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first and the only line of each test case contains a string ‘STR’.
Output Format :
For each test case, print ‘1’ if given ‘STR’ is complex else print ‘0’.
Print the output of each test case in a separate line.
Note: You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 100
1 <= |STR| <= 5000
Where ‘T’ denotes the total number of test cases, |STR| represents the length of ‘STR’.
Time Limit: 1 second
Approaches
The idea is to use the stack as using this, we can easily keep track of the expression between ‘(‘ and ‘)’ brackets. Basically, if we are able to find an expression surrounded by ‘(‘ and ‘)’, and if we are again left with ‘(‘ and ‘)’ as part of the ‘STR’, it implies there must be some unnecessary multiple brackets.
For example for ‘STR’ = “((a+b))”, after getting the expression “(a+b)” from the stack, we will be left with “()” which is an unnecessary bracket pair.
Here is the algorithm:
Create a stack of a type character. Iterate through ‘STR’ and for each character in the expression do the following:
- If the character is an open bracket ‘(‘ or any operator or operand, we push it into the stack.
- If the character is close bracket ‘)’, then pop characters from the stack until we get open bracket ‘('.
Following two cases can arise while popping from the stack-
- If the element at the top of the stack is an open parenthesis ‘(‘, then we have found a duplicate bracket. For example, “(((a+b))+c)” has redundant brackets around ‘a+b’. When we reach “)” at index 7(0-based indexing), we have “((” in the stack. Since the top of the stack is an opening bracket, we conclude that there are duplicate brackets.
- If the element at the top of the stack doesn’t have any operand (‘*’, ‘+’, ‘/’, ‘-‘) then it indicates the presence of unwanted brackets surrounded by expression. For instance, “(a)+b” contains unwanted ‘()’ around ‘a’ thus it is redundant.