241. Design priorities for operational expressions

241. Design priorities for operation expressions

Original title link ：https://leetcode.cn/problems/different-ways-to-add-parentheses/

Give you a string of numbers and operators expression , Combine numbers and operators according to different priorities , Calculate and return the results of all possible combinations . You can In any order Return to the answer .

Example 1：

Input ：expression = “2-1-1”
Output ：[0,2]
explain ：
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2：

Input ：expression = “23-45”
Output ：[-34,-14,-10,-10,10]
explain ：
(2*(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)*5) = 10

Tips ：

1 <= expression.length <= 20
expression By numbers and operators ‘+’、‘-’ and ‘*’ form .
All integer values in the input expression are in the range [0, 99]

Their thinking ：

Divide and conquer algorithm , Bounded by operators , Divided into left and right subexpressions , I'll go on , Until it's a number （ End of recursion flag ）, Then judge the operator to merge .

Code implementation ：

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        #  End of recursion flag ： Only numbers , Return the number directly 
        if expression.isdigit():
            return [int(expression)]

        ans = []

        for i, c in enumerate(expression):
            #  Split when encountering operators , Calculate the values of the left and right subexpressions respectively 
            if c in "+-*":
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i + 1:])

                #  Combine the values of the numerator expression 
                for l in left:
                    for r in right:
                        if c == '+':
                            ans.append(l + r)
                        if c == '-':
                            ans.append(l - r)
                        if c == '*':
                            ans.append(l * r)
        return ans

reference ：
https://leetcode.cn/problems/different-ways-to-add-parentheses/solution/pythongolang-fen-zhi-suan-fa-by-jalan/