Different Ways To Add Parenthesis

Easy

0/40

Average time to solve is 10m

Contributed by

5 upvotes

Asked in companies

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 )

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

Hint 1

Brute Force, Can we use recursion to try all the parentheses possible?

Approaches (1)

Approach 1

Recursive Brute Force

We will go through the string S from left to right if we encounter an operator we will split S across the operator and recursively solve the expression before the operator and after the operator. Then use the results of the left part and the right part to create the answer for expression.

The algorithm will be-

If S is a single integer return the number.
We will store the answer in an array/list ANS.
We will iterate over the S.
1. If the current character of S is an operator.
  1. Recursively solve the left side and right side of the operator.
  2. Apply the current operator on the results of the left side and right side.
  3. Store the results in ANS.
Return the array/list ANS

Time Complexity

O(2 ^ N), where ‘N’ the number of operators in ‘S’.

The number of all valid expressions is necessarily given by the Catalan numbers. As the Catalan number for any N is of order O(2 ^ N), time complexity will be O(2 ^ N).

Space Complexity

O(2 ^ N), where ‘N’ the number of operators in ‘S’.

The space complexity due to the recursion stack will be O(2 ^ N).

(100% EXP penalty)

Different Ways To Add Parenthesis

Console