class Solution:
def diffWaysToCompute(self, expression):
# 如果只有數字,直接返回
if expression.isdigit(): # 判斷是否都為數字
return [int(expression)]
res = []
for i, char in enumerate(expression):
if char in ['+', '-', '*']:
# 1.分解:遇到運算符,計算左右兩側的結果集
# 2.解決:diffWaysToCompute 遞歸函數求出子問題的解
left = self.diffWaysToCompute(expression[:i]) # 不包含i的
right = self.diffWaysToCompute(expression[i+1:]) # 包含i+1
# 3.合並:根據運算符合並子問題的解
for l in left:
for r in right:
if char == '+':
res.append(l + r)
elif char == '-':
res.append(l - r)
else:
res.append(l * r)
return res
expression = "2-1-1"
a = Solution.diffWaysToCompute(expression) # 這樣直接調用是錯誤地,它提示少一個self的參數,用下面這個S = Solution()先實例化類就可以忽略self了。
# 下面這樣是正確的
S = Solution()
a = S.diffWaysToCompute(expression)
print(a)