leetcode241 为运算表达式设计优先级

class Solution(object):

    def diffWaysToCompute(self, input):

        """

        :type input: str

        :rtype: List[int]

        """

        #一个函数calc做运算，

        #一个字典memo记录已经有的结果,key为输入字符串，value为所有计算结果组合

        #遍历input,以一个运算符为界，对左右两边进行计算，得到所有组合后返回，并进行排列组合计算

        #递归边界为input为数字

        if input.isdigit():

            return [int(input)]

        memo={}

        res=[]

        if input in memo:

            return memo[input]

        for i in range(len(input)):

            op=input[i]

            if op not in "+-*":

                continue

            left=self.diffWaysToCompute(input[:i])

            right=self.diffWaysToCompute(input[i+:])

            for num1 in left:

                for num2 in right:

                    res.append(self.calc(num1,num2,op))

        memo[input]=res

        return res

    def calc(self,num1,num2,op):

        if op=="+":

            return num1+num2

        elif op=="-":

            return num1-num2

        else:

            return num1*num2