Leetcode-282-Expression Add Oper

在数字构成的字符串中加入加减乘三种符号来使表达式的值等于目标值。题目要求给出所有可能的表达式，因此要用搜索的方法，而这题显然使用DFS更方便，这题的代码我大体写出来了，但是有一个坎没想清楚，那就是乘号的优先级问题，举例来说，如果我只允许在式子中插入加减符号，则DFS过程很简单，大概形式如下：

void dfs(string& s, int target, int pos, long cv, string r, vector<string>& res) 
{
      if (pos == s.size() && cv == target) 
      {
          res.push_back(r);
          return;
      }
      for (int i = 1; i <= s.size() - pos; i++) 
      {
          string t = s.substr(pos, i);
          if (i > 1 && t[0] == '0') continue; // preceding 
          long n = stol(t);
          if (pos == 0) 
          {
              dfs(s, target, i, n, n, t, res);
              continue;
          }
          dfs(s, target, pos+i, cv+n, r+"+"+t, res);
          dfs(s, target, pos+i, cv-n, r+"-"+t, res);
      }
}

也就是说，我们只需每次遍历各个可能划分的点（即在什么位置插入符号），然后插入符号后记录当前计算的值，然后从未计算过的位置开始递归即可。

但这题麻烦的地方在于乘法，直接按上述思路计算无法解决的情况，因为在DFS中我们会先计算，然后得到结果后再计算，如何在DFS中正确地引入乘法呢？

从https://leetcode.com/problems/expression-add-operators/discuss/71898/17-lines-solution-dfs-(C%2B%2B)的解法找到了答案——引入一个记录上一步计算的第二个值（若上一步是1+2则记录2，若是1-2则记录-2）。

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        dfs(num, target, 0, 0, 0, "", res);
        return res;
    }
    
    void dfs(string& s, int target, int pos, long cv, long pv, string r, vector<string>& res){
        if (pos == s.size() && cv == target) {
            res.push_back(r);
            return;
        }
        for (int i = 1; i <= s.size() - pos; i++) {
            string t = s.substr(pos, i);
            if (i > 1 && t[0] == '0') continue; // preceding 
            long n = stol(t);
            if (pos == 0) {
                dfs(s, target, i, n, n, t, res);
                continue;
            }
            dfs(s, target, pos+i, cv+n, n, r+"+"+t, res);
            dfs(s, target, pos+i, cv-n, -n, r+"-"+t, res);
            dfs(s, target, pos+i, cv-pv+pv*n, pv*n, r+"*"+t, res);
        }
    }
};

关键行其实只有三行：

dfs(s, target, pos+i, cv+n, n, r+"+"+t, res);
dfs(s, target, pos+i, cv-n, -n, r+"-"+t, res);
dfs(s, target, pos+i, cv-pv+pv*n, pv*n, r+"*"+t, res);

我们来看看是如何发挥作用的，举个例子，比如我们要计算，在算法中其实就是：

cv=1+2, pv=2
cv=(1+2)-2+2*3,pv=2*3
cv=(1+2)-2+2*3-2*3+2*3*4,pv=2*3*4

从上述过程我们可以看到，在上一步是加减运算时记录第二个值的意义就在于后面我们可以回溯到加法或减法这个点，更新加减运算的第二个值（因为第二个值遇到了优先级更高的乘法）。

通过这题可以了解到DFS+Backtracking的用法。