为运算表达式设计优先级

---

image.png

给定一个算式：1 + 2 * 3 - 4 * 5

请问，这个算式有几种加括号的方式？显然我们有四种加括号方式：

(1) + (2 * 3 - 4 * 5)
(1 + 2) * (3 - 4 * 5)
(1 + 2 * 3) - (4 * 5)
(1 + 2 * 3 - 4) * (5)

其实就是按照运算符进行分割，给每个运算符的左右两部分加括号，如果运气好可以修改到优先级，不过也可能一个优先级也没改到，（（2） -（1））-（1）就相当于（2-1-1）的作用弄了个覆盖所有的大括号。

2-（1-1），（2-2）*（1）

有人可能会问：1 + 2 * （3 - 4） * 5怎么没有？因为它可以由（1 + 2 * （3 - 4 ) ) * 5 => （1 + 2 * （3 - 4 ) ) * 5得到。

• 本示例将 str 拆分成 []，也可以不拆，随缘。用了备忘录避免重复计算。

class Solution:
    def __init__(self):
        self.d={}
    def helper(self,ex,starts,ends):
        if starts==ends:
            return [int(ex[starts])]
        if starts>ends:
            return 0
        if "".join(ex[starts:ends+1]) in self.d:
            return self.d["".join(ex[starts:ends+1])]
        res=[]
        for i in range(starts,ends+1):
            if ex[i].isdigit()==False:
                a=self.helper(ex,starts,i-1)
                b=self.helper(ex,i+1,ends)
                for j in a:
                    for k in b:
                        if ex[i]=="+":
                            res.append(j+k)
                        elif ex[i]=="-":
                            res.append(j-k)
                        elif ex[i]=="*":
                            res.append(j*k)
        self.d["".join(ex[starts:ends+1])]=res
        return res
    def diffWaysToCompute(self, expression: str) -> List[int]:
        ex=[]
        string=""
        for i in expression:
            if i.isdigit():
                string+=i
            else:
                ex.append(string)
                ex.append(i)
                string=""
        ex.append(string)
        return self.helper(ex,0,len(ex)-1)