题目：为运算表达式设计优先级

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

示例 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

来源：力扣（LeetCode）第241题

链接：https://leetcode-cn.com/problems/different-ways-to-add-parentheses

## 分析： - 动态规划+分治算法。 - 当只有一个运算符时，只有一种情况，当有两个运算符时有两种情况，以此类推。 - 当有三个运算符时，假设第一个运算符优先级最高，然后剩下三个数有两种情况，将两种情况与其相加，得到答案。接着判断第二个运算符优先级最低时，依次类推。

代码：

from functools import lru_cache  # lru缓存淘汰算法。
class Solution:
    @lru_cache(None)
    def diffWaysToCompute(self, input: str) -> List[int]:
        if input.isdigit():  # 基线条件
            return [int(input)]
        opt = {'-', '+', '*'}  # 运算符集合
        ans = []  # 储存答案
        for i, char in enumerate(input):  # 判断每个运算符优先级最低的时候。
            if char in opt:  # 如果是运算符才执行
                left = self.diffWaysToCompute(input[:i])  # 拿到运算符的左边，递归
                right = self.diffWaysToCompute(input[i+1:])  # 拿到运算符的右边，递归
                ans.extend([self.operator(l, r, char) for l in left for r in right])  # 将运算符的左右两边的值按照运算符做运算。left和right拿到的是列表，就像前面说的，如果左边有不止一个运算符时答案也不止一个，右边同理。
        return ans
    def operator(self, l, r, char):  # 根据运算符做运算符操作，char就是运算符。
        if char == '-':
            return l - r
        elif char == '+':
            return l + r
        else:
            return l * r

复杂度分析：

• 时间复杂度：O(n!)n为运算符的个数，个人认为
• 空间复杂度：实在算不出来了。。。。