Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Different Ways To Add Parenthesis

Easy
0/40
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in companies
FlipkartGoMechanic

Problem statement

You are given a string 'S' containing an arithmetic expression. Your task is to return all the possible results obtained after putting the valid parenthesis.

It is guaranteed that the given string only contains the ‘+’, ‘-’, ‘*’ operator.

The valid expression is an expression where a number of closing and opening parenthesis is the same. And the result is computed by solving inner parentheses first.

For example:
S = 2 * 3 - 2
((2 * 3) - 2) = 4
(2 * (3 - 2)) = 2 , [4, 2] or [2, 4] are the solution.
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 10
3 <= len(S) <= 65

len(S) is the length of the string 'S' it is guaranteed that input has at least one operator.  

Time Limit: 1 sec.
Sample Input 1:
2
1+2*3+1
1+1*2
Sample Output 1:
9 8 12 8 10
3 4
Explanation of Sample Input 1:
For first test case output is [9,8,12,8,10] as,
((1 + 2) * (3 + 1)) = 9
((1 + (2 * 3)) + 1) = 8
((1 + 2) * (3 + 1)) = 12
(1 + ((2 * 3) + 1)) = 8
(((1 + 2) * 3) + 1) = 10

For the second test case output is [3, 4] or [4,3] as
((1 + 1) * 2) = 4
(1 + (1 * 2)) = 3
Sample Input 2:
2
1+1-1-1
13*1
Sample Output 2:
2 2 0 0 0
13
Full screen
Console