Leetcode 241: Different Ways to Add Parentheses

Problem Description:
Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

Example 1:
Input: expression = “2–1–1”
Output: [0,2]
Explanation:
((2–1)-1) = 0
(2-(1–1)) = 2

Example 2:
Input: expression = “2*3–4*5” Output: [-34,-14,-10,-10,10]

Explanation:

(2*(3-(45))) = -34
((23)-(45)) = -14
((2(3–4))5) = -10
(2((3–4)5)) = -10
(((23)-4)*5) = 10

Step1:

At first, we need to convert the expression that is in the form of a string into the list.
We cannot directly convert by using list() because in that case: “34” will be translated as [3,4] which is incorrect.

The approach for this will be to get the number, multiply by 10 and add with the next number.

expression = "20+30-40*50"
s_li = []
flag = True
for ch in expression:
    if ch.isdigit() and flag:
        s_li.append(int(ch))
        flag = False
    elif ch.isdigit() and not flag:
        s_li[-1] = s_li[-1]*10 + int(ch)
    else:
        s_li.append(ch)
        flag = True
s_li
[20, '+', 30, '-', 40, '*', 50]

Step2:

Now we, need to evaluate the expression

Again to evaluate the expression, we will use the processed and unprocessed methods.

Refer, to previous blogs to understand the processed and unprocessed methods.

We will divide the expression by selecting the operator. The left part of the operand will go into the unprocessed part and the right part will go into the processed part. Again, we will take the bigger expression and divide it from the operand. The below image represents that particular thing.

We divide the expression until we have one operand on the left and one operand on the right.

Based, on this information the recursive function call will become as follow:

def fun(s):
    
    #Return back when we have only one operator#
    if len(s) == 1:
        return s
    
    #We are dividing with 2 because we are taking operands and operator pair#
    #In above image, the length of string is 7 but we are doing 3 calls (in BFS)#
    for i in range(len(s)//2):
        lft_operand, operator, rght_operand = None, None, None

fun(s_li)

Now, we need to form the equation by which we can make the unprocessed and processed part.

So, you can see over here for the left operand the equation goes in the form of [0], [0,2], [0,4]. So the logic for this will be, s[0:i*2+1]

Similarly, for operator, it is the next index of the ith value so it will be simply, s[i*2+1]

Lastly, the right operator it is following the sequence of [2,6], [4,6] and [6]. So we can form the logic as, s[i*2+2::]

def fun(s):
    
    #Return back when we have only one operator#
    if len(s) == 1:
        return s
    
    #We are dividing with 2 because we are taking operands and operator pair#
    #In above image, the length of string is 7 but we are doing 3 calls (in BFS)#
    for i in range(len(s)//2):
        lft_operand, operator, rght_operand = fun(s[:i*2+1]), s[i*2+1], fun(s[i*2+2:])
        print(lft_operand, operator, rght_operand)

fun(s_li)
[40] * [50]
[30] - None
[30] - [40]
None * [50]
[20] + None
[20] + [30]
[40] * [50]
None - None
[30] - [40]
[20] + None
[20] + [30]
None - [40]
None * [50]

Now, we need to apply the logic of backtracking.
For, this we need to evaluate the expression. Moreover, as you can see over here the recursion tree possesses more than one node on the left as well as right. So we need to evaluate by considering it.

As highlighted over here,

def fun(s):
    
    #Return back when we have only one operator#
    if len(s) == 1:
        return s
    
    #We are dividing with 2 because we are taking operands and operator pair#
    #In above image, the length of string is 7 but we are doing 3 calls (in BFS)#
    for i in range(len(s)//2):
        lft_operand, operator, rght_operand = fun(s[:i*2+1]), s[i*2+1], fun(s[i*2+2:])
        
        for op1 in lft_operand:
            for op2 in rght_operand:
                
                #Evaluation logic will goes over here# 

fun(s_li)

Writing the evaluation logic:

def fun(s):
    
    #Return back when we have only one operator#
    if len(s) == 1:
        return s
    
    res = []
    #We are dividing with 2 because we are taking operands and operator pair#
    #In above image, the length of string is 7 but we are doing 3 calls (in BFS)#
    for i in range(len(s)//2):
        lft_operand, operator, rght_operand = fun(s[:i*2+1]), s[i*2+1], fun(s[i*2+2:])
        
        
        
        #Considering all the left and right operand#
        for op1 in lft_operand:
            for op2 in rght_operand:
                
                #Evaluation logic#
                if operator == '+':
                    res.append(output_left + output_right)
                if operator == '-':
                    res.append(output_left - output_right)
                if operator == '*':
                    res.append(output_left * output_right)
    
    return res

fun(s_li)

The code successfully runs and it is 73% faster.

Thank you for reading my blogs!

~ Pritul Dave.