241. Different Ways to Add Parentheses 🔥

Medium

Problem:

Receive numbers and operators as input and print out the results of all possible combinations.

Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

https://leetcode.com/problems/different-ways-to-add-parentheses/

What to learn:

eval()

The eval() function parses a string and evaluates it as a Python expression.

>>> '4+5'
'4+5'
>>> eval('4+5')
9

append() vs. extend()

when inserting another list into a list:

• append() treats the entire list as another element and adds it to the list.

• In contrast, extend() unpacks the list being inserted and expands each of its elements into the list.

>>> a = [1,2,3]
>>> b = [4,5]
>>> a.append(b)
>>> a
[1, 2, 3, [4, 5]]

>>> a = [1,2,3]
>>> b = [4,5]
>>> a.extend(b)
>>> a
[1, 2, 3, 4, 5]

Solution:

When the operators '*', '-', or '+' appear, the algorithm divides the expression into left and right parts and then returns the results of each calculation.

For instance, the expression '3-4*5' can have multiple calculation results such as -17 and -5. Ultimately, it returns the results of 2 * [-17, -5], which are [-34, -10].

1. The expression is recursively divided at each operator into left and right parts, and the divided values are calculated using a compute() function. The results are then expanded using extend() instead of append(). This is because the insertion target can be multiple values, so extend() is used to unfold and insert them.

2. Since the values could be in multiple forms just before the final calculation, each value is extracted iteratively as a singular form for calculation.

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        def compute(left, right, op):
            results = []
            for l in left:
                for r in right:
                    results.append(eval(str(l) + op + str(r)))
            return results
    
        if expression.isdigit():
            return [int(expression)]

        results = []
        for index, value in enumerate(expression):
            if value in "-+*":
                left = self.diffWaysToCompute(expression[:index])
                right = self.diffWaysToCompute(expression[index+1:])

                results.extend(compute(left, right, value))
        return results