LeetCode | 241.为运算表达式设计优先级
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。
示例 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
提示：
- 1 <= expression.length <= 20
- expression 由数字和算符 '+'、'-' 和 '*' 组成。
- 输入表达式中的所有整数值在范围 [0, 99]
思路：
带备忘录的动态规划，用小问题的解去计算大问题。一开始还没想到怎么写，陷入的表达式的分解，一看到表达式是字符串，就去想怎么解析表达式，用什么保存数字，用什么保存操作符了。
其实不需要关心这些，只需要遍历字符串，对每个操作符两边的表达式可能的结果做组合就行。
vector<int> diffWaysToCompute(string expression) {
unordered_map<string, vector<int>> mp;
return helper(mp, expression);
}
vector<int> helper(unordered_map<string, vector<int>> &mp, string str) {
vector<int> result;
for (int i = 0; i < str.size(); ++i) {
char ch = str[i];
if (ch == '+' || ch == '-' || ch == '*') {
vector<int> l, r;
// 计算左边的表达式所有可能的结果
string left = str.substr(0, i);
if (mp.count(left))
l = mp[left];
else
l = helper(mp, left);
// 计算右边的表达式所有可能的结果
string right = str.substr(i + 1, str.size());
if (mp.count(right))
r = mp[right];
else
r = helper(mp, right);
// 左右两边表达式所有的结果进行合并
for (auto & i : l) {
for (auto &j : r) {
if (ch == '+')
result.push_back(i + j);
else if (ch == '-')
result.push_back(i - j);
else
result.push_back(i * j);
}
}
}
}
if (result.size() == 0)
result.push_back(stoi(str));
mp[str] = result;
return result;
}