Different Ways To Add Parenthesis

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.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first and only line of each test case contains arithmetic expressions containing numbers and  ‘+’, ‘-’, ‘*’ as operators.

Output Format:

For each test case print all the values that can be obtained from the expression after putting valid parenthesis.

You can print values in any order.

The output for each test case will be printed in a separate line.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

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