/*
 * @lc app=leetcode.cn id=241 lang=cpp
 *
 * [241] 为运算表达式设计优先级
 */

// @lc code=start
class Solution {
public:
    unordered_map<string, vector<int>> memo;
    vector<int> diffWaysToCompute(string expression) {
        if (memo.find(expression) != memo.end()) {
            return memo[expression];
        }
        if (expression.find_first_of("+-*") == expression.npos) {
            return {stoi(expression)};
        }
        vector<int> ans;
        int pos = 0;
        while ((pos = expression.find_first_of("+-*", pos + 1)) != expression.npos) {
            vector<int> left = diffWaysToCompute(expression.substr(0, pos)), right = diffWaysToCompute(expression.substr(pos + 1));
            for (int l : left) {
                for (int r : right) {
                    ans.emplace_back(expression[pos] == '+' ? l + r : expression[pos] == '-' ? l - r : l * r);
                }
            } 
        }
        memo[expression] = ans;
        return memo[expression];
    }
};
// @lc code=end