LeetCode241. 为运算表达式设计优先级（python）

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2:

输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释: 
(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

先附代码

class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:
        end = []
        op = {'+':lambda x,y:x+y, 
              '-':lambda x,y:x-y,
              '*':lambda x,y:x*y}
        
        for i in range(len(input)):
            if input[i] in op.keys():
                for left in self.diffWaysToCompute(input[:i]):
                    for right in self.diffWaysToCompute(input[i+1:len(input)]):
                        output = op[input[i]](left, right)
                        end.append(output)
        
        if len(end) == 0:
            end.append(int(input))
        
        return end

解题思路：

分治算法 + 递归

函数diffWaysToCompute，先定义了列表end（存储结果），字典op（存储运算），对函数接受的字符串进行遍历，在当前字符为运算符时以运算符为界将字符串分为L和R（如上图），再对L和R进行递归。如果当前字符串中没有运算符，也就是end为空时就算达到了“边界”，返回当前字符串的int类型

简单的说函数返回的就是当前字符串运算的所有可能性,diffWaysToCompute（“2”）返回的是end=[2]，diffWaysToCompute（“4*5”）返回的为end = [20]；diffWaysToCompute（“3-4*5”）返回的是end=[-18, -5]