Different Ways To Add Parenthesis

Posted: 6 Mar, 2021
Difficulty: Easy


Try Problem

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.
You don’t need to print anything. It has already been taken care of. Just implement the given function.
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.
Approach 1

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-

  1. If S is a single integer return the number.
  2. We will store the answer in an array/list ANS.
  3. 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.
  4. Return the array/list ANS
Try Problem