Ninja And A Complex Expression

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
5 upvotes
Asked in company
HSBC

Problem statement

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?

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
3
(a+b)
((a+b))
((a+b)*(c+d))
Sample Output 1 :
0
1
0

Explanation for Sample Output 1 :

For sample test case 1: 
In this sample test case, the given input string is already simplified because it is not containing any unnecessary multiple brackets. 

For sample test case 2: 
In this sample test case, the given input string “((a+b))” is complex and can be simplified as after removing the unnecessary multiple brackets ‘STR’ will become “(a+b)”

For sample test case 3: 
In this sample test case, the given input string is already simplified because it is not containing any unnecessary multiple brackets.
Sample Input 2 :
3
(a*(b+c))
((a+((c+d))))
((a*b)+((c+d)+(e/f)))
Sample Output 2 :
0
1
0

Explanation for Sample Output 2 :

For sample test case 1: 
In this sample test case, the given input string is already simplified because it is not containing any unnecessary multiple brackets. 

For sample test case 2:
In this sample test case, the given input string “((a+((c+d))))” is complex and can be simplified as after removing unnecessary multiple brackets ‘STR’ will become “(a+c+d)”.

For sample test case 3: 
In this sample test case, the given input string is already simplified because it is not containing any unnecessary multiple brackets.
Hint

Try to use the data structure with Last In and First Out.

Approaches (1)
Using Stack

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.
Time Complexity

O(|STR|), where |STR| is the length of the given string ‘STR’.

 

Because we are iterating each element exactly once. Hence overall time complexity is O(|STR|).

Space Complexity

O(|STR|), Where |STR| is the length of the given string ‘STR’.

 

Because in the worst-case size of the stack will be |STR|. Hence overall space complexity will be |STR|.

Code Solution
(100% EXP penalty)
Ninja And A Complex Expression
Full screen
Console