表达式添加运算符

表达式添加运算符

给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

DFS应用：

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        if (num.empty()) return result;
        for (int i = 0; i < num.size(); i++) num_after.emplace_back(stoll(num.substr(i)));
        exp.resize(num.size() * 2);
        dfs(num, target, 0, 0, 0, 1);
        return result;
    }
private:
    string exp;
    vector<string> result;
    vector<long long> num_after;

    int dfs(string& num, long long target, int exp_p, int pos, long long now, long long last) {
        now = now * 10 + num[pos] - '0';
        exp[exp_p++] = num[pos];
        long long cur_val = now * last;
        if (pos == num.size() - 1) {
            if (target == cur_val) result.emplace_back(exp.substr(0, exp_p));
            return 0;
        }
        exp[exp_p] = '*';
        dfs(num, target, exp_p + 1, pos + 1, 0, cur_val);
        if (num_after[pos + 1] >= abs(target - cur_val)) {
            exp[exp_p] = '+';
            dfs(num, target - cur_val, exp_p + 1, pos + 1, 0, 1);
            exp[exp_p] = '-';
            dfs(num, target - cur_val, exp_p + 1, pos + 1, 0, -1);
        }
        if (now) dfs(num, target, exp_p, pos + 1, now, last);
        return 0;
    }
};