题目链接：241. 为运算表达式设计优先级
分治法，几点优化：
- 用
functools.cache避免重复运算； - 用正则简化分词；
- 用
itertools.product方法简化迭代。
import re
from functools import cache
from itertools import product
from typing import List
class Solution:
@cache
def diffWaysToCompute(self, expression: str) -> List[int]:
if expression == '':
return []
if expression.isdigit():
return [int(expression)]
def operate(l: int, r: int, op: str) -> int:
if op == '+':
return l + r
elif op == '-':
return l - r
elif op == '*':
return l * r
else:
raise ValueError('op invalid')
ret = []
for op in re.finditer(r'[+\-*]', expression):
opl, opr = op.span()
ls, rs = self.diffWaysToCompute(expression[:opl]), self.diffWaysToCompute(expression[opr:])
if ls and rs:
ret.extend(operate(l, r, op.group()) for l, r in product(ls, rs))
return ret