LeetCode0241.添加括号的不同方式设计运算表达式的优先级【中】【Python】【分而治之】问题LeetCode给定一串数字和运算符，返回所有可能的计算结果对数字和运算符进行分组的所有不同可能方式。有效的运算符是+、-和*。示例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给定一个包含数字和运算符的字符串，给表达式加上括号，改变其运算的优先级，得到不同的结果。您需要给出所有可能组合的结果。有效的运算符包括+、-和*。示例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思想分治循环遍历，如果当前位置是运算符，则分别计算左右公式的值，然后与运算符拼接在一起。时间复杂度:O(n)Python3代码classSolution:defdiffWaysToCompute(self,input:str)->List[int]:#solution:divideandconquerifinput.isdigit():#inputonlycontainsdigitalreturn[int(输入)]n=len(输入)res=[]foriinrange(n):ifinput[i]in'+-*':lefts=self.diffWaysToCompute(input[:i])rights=self.diffWaysToCompute(input[i+1:])forleftinlefts:forrightinrights:ifinput[i]=='+':res.append(left+right)elifinput[i]=='-':res.append(left-right)elifinput[i]=='*':res.append(left*right)##使用eval#res.append(eval(str(left)+input[i]+str(right)))returnres代码地址GitHub链接
