@(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
解题思路
这里的题意是忽略运算符优先级，找出所有可能的数字与运算符的结合方式，再计算其结果。
栗子分析
我的思路是由分析栗 2 得出的，让我们再来整理一下栗 2 的结果。
表达式为："2*3-4*5"。
所有可能的组合方式如下，我稍微整理了下。
// 第一组组合。由第一个操作符 '*' 连接左右两边的组合
2*(3-(4*5)) = -34
2*((3-4)*5) = -10
// 第二组组合。由第二个操作符 '-' 连接左右两边的组合
(2*3)-(4*5) = -14
// 第三组组合。由第三个操作符 '*' 连接左右两边的组合
(2*(3-4))*5 = -10
((2*3)-4)*5 = 10
从上，我们可以发现一些规律。
第一组组合由 '*' 分隔表达式；第二组组合由 '-' 分隔；第三组组合由 '*' 分隔，且从整体上来看将表达式分成了左右两部分。再细看左右两部分，不难发现：
- 如果左/右两部分是表达式，则继续按照上述方式进行分解组合。
- 如果左/右两部分是数字，则不再分解。
比如：2*(3-4*5)，其右边部分 (3-4*5) 是个表达式，又可分解组合如下：
3-(4*5)
(3-4)*5
而左边 2 是数字，不可再分解。因此，2*(3-4*5) 所有的组合方式为：
2*(3-(4*5))
2*((3-4)*5)
再来看个复杂些的栗子。
比如某个表达式为：(2-1*3)*(3-4*5)，中间的 '*' 将表达式分为 (2-1*3) 与 (3-4*5)。
其中左边表达式 (2-1*3) 的组合方式如下：
2-(1*3) = -1
(2-1)*3 = 3
右边表达式 (3-4*5) 的组合方式如下：
3-(4*5) = -17
(3-4)*5 = -5
那么该表达式的所有组合方式有 2 * 2 = 4 种，为左右组合方式的两两组合。如下所示：
(2-(1*3))*(3-(4*5)) = -1 * -17 = 17
((2-1)*3)*(3-(4*5)) = 3 * -17 = -51
(2-(1*3))*((3-4)*5) = -1 * -5 = 5
((2-1)*3)*((3-4)*5) = 3 * -5 = -15
因此，以上的结论可表述为：表达式的组合方式 =「左边表达式可能的组合」* 「右边表达式可能的组合」，即再次两两组合。
弄清楚如何进行组合，那么下一步就是计算组合的运算结果。
何时能计算结果？当分解到左右两边都为数字时，这时候就需要计算结果了。根据中间操作符，左右两边的数字即可运算得出。但是要注意一点，由于组合方式有多种，那么组合计算的结果也有多个，需要用数组保存。
对于上述栗子 (2-1*3)*(3-4*5)，其所有组合的值为：
// 两个数组元素两两相乘
[-1, 3] * [-17, -5] = [17, 5, -51, -15]
所以，我们也能得出如下结论：表达式所有组合的值 = 「左边表达式组合的值」op「右边表达式组合的值」。其中 op 代表操作符。
思路总结
根据以上栗子的讲解，我们总结一下思路：
- 首先将整个表达式看成只有两部分组成，由一个操作符隔开。
- 遍历表达式中所有的操作符，根据不同位置的操作符将其划分为两部分。
- 选定一个操作符，该操作符会将表达式分为左右两部分。如果左/右部分也是一个表达式，则继续按上述方式分解。最终的组合为左右两部分结果的再次两两组合。
- 由于子表达式会有多个组合，所以需要用数组保存所有组合方式运算后的值。为了一致性处理，即使只是单个值，也要以数组形式返回。
- 表达式所有组合的值为「左表达式所有组合的值」与「右表达式所有组合的值」两两运算。
具体实现
理清思路后，有没有暗暗感觉到这是一道递归算法题，因为子表达式也以相同方式进行分解组合。
实现就比较简单了，但是要注意几个地方。
- 表达式分解后，对数字的判断。因为这里我犯了个低级的错误，受题目栗子影响，误认为当表达式长度为
1时就是数字。(⊙o⊙)。 - 考虑当表达式不存在操作符时的边界条件。这时不能将表达式分为两部分，要注意这里的处理。
- 可将表达式计算的结果缓存，防止重复计算。
核心代码如下：
// start 代表字符串左边界，end 代表字符串右边界
var recursive2 = function (input, start, end) {
if (start < 0 || end > input.length || start > end)
{
return []
}
// 取出子表达式
const substr = input.slice(start, end + 1)
// 如果有缓存
if (map.has(substr)) {
return map.get(substr)
}
let resultList = []
let i = start
while (i <= end) {
const op = input[i]
if (op === '+' || op === '-' || op === '*') {
// 分别计算左/右两边的值
const leftPartResult = recursive(input, start, i - 1)
const rightPartResult = recursive(input, i + 1, end)
// 运算符函数
const opFunc = opMap[op]
// 两个数组做运算
leftPartResult.forEach(left => {
rightPartResult.forEach(right => {
const result = opFunc(left, right)
resultList.push(result)
})
});
}
i += 1
}
// 说明是数字
if (resultList.length === 0) {
// 以 [num] 方式返回
resultList.push(parseInt(substr))
}
// 缓存
map.set(substr, resultList)
return resultList
}
