分治法
分治算法三步走：
- 分解: 按运算符分成左右两部分，分别求解
- 解决: 实现一个递归函数，输入算式，返回算式解
- 合并: 根据运算符合并左右两部分的解，得出最终解
1. 例题
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
示例 1：
输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2：
输入：expression = "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
function diffWaysToCompute(expression: string): number[] {
const ans: number[] = []
let flag = true
for (let i = 0; i < expression.length; i++) {
const char = expression[i]
if (['+', '-', '*'].includes(char)) {
flag = false
const left = diffWaysToCompute(expression.substring(0, i))
const right = diffWaysToCompute(expression.substring(i + 1))
for (let l = 0; l < left.length; l++) {
for (let r = 0; r < right.length; r++) {
ans.push(calc(left[l], char, right[r]))
}
}
}
}
if (flag) {
return [parseInt(expression, 10)]
}
return ans
}
function calc(left: number, char: string, right: number): number {
switch (char) {
case '+':
return left + right
case '-':
return left - right
case '*':
return left * right
}
}