LeetCode | 241.为运算表达式设计优先级

  给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

  生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10⁴ 。

示例 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;
}