LeetCode Expression Add Operators：SLR(1)、meet-in-the-middle及其他

题目描述

Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

1
2
3
4
5
6
Examples:
"123", 6 -> ["1+2+3", "1*2*3"]
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

Credits: Special thanks to @davidtan1890 for adding this problem and creating all test cases.

分析

枚举所有位置的符号(并置、+、-、*)后转化为表达式求值。加速的办法是让枚举和求值一起进行。

考虑题目要求的文法： 

1
2
3
4
E ::= E "+" F | E "-" F
F ::= F "*" L
L ::= "0" | L1
L1 ::= "1" | ... | "9" | L1 "0" | ... | L1 "9"

使用不考虑前导0的简化文法。我们会采用递归算法，形似recursive descent parser，在递归过程中不难采取一些措施避免生成前导0。 

1
2
3
E ::= E "+" F | E "-" F
F ::= F "*" L
L ::= "0" | ... | "9" | L "0" | ... | L "9"

Parse tree以0~9为叶子，+、-、并置(下面用@表示)为内部节点，其最右节点到根的距离小于等于3，之后会说明原因。对于某一前缀的parse tree，添加一个符号和一个数字后会得到一棵新的parse tree，这一过程可以看作在二叉树中添加一中序遍历序号最大的节点(类似于Cartesian tree线性构造算法)。取决于添加的符号，可能有以下三种变化。最左边为原先的parse tree，后面三棵为添加不同符号后得到的parse tree： 

1
2
3
4
5
6
7
8
9
  +         +         +           +
 / \       / \       / \         / \
2   *     2   *     2   *       +   6
   / \       / \       / \     / \
  3   @     3   @     *   6   2   *
     / \       / \   / \         / \
    4   5     @   6 3   @       3   @
             / \       / \         / \
            4   5     4   5       4   5

我们给parse tree每个节点设置semantic value，即对应的表达式的结果。因为节点按照中序遍历顺序添加，任何左子树的结构不会再发生变化，可以把整棵子树收缩成一个节点。@是文法优先级最高，也可以规约，即把对应子树收缩。上面的四棵树收缩后变成下面这样： 

1
2
3
4
5
  +         +         +           +
 / \       / \       / \         / \
2   *     2   *     2   *      137  6
   / \       / \       / \
  3   45    3  456   135  6

文法中的三个产生式有层级关系，高优先级符号的子树中没有低优先级符号，这就是任意节点到根距离小于等于3的原因。从另一个角度看，LR(0)项集是无圈的，最长路径长度为3。枚举并求parse tree的过程很像SLR(1)，又像Earley parser。

-可以看作+，同时把右边的数字视为相反数。这样，我们得到的tree只剩下+ *两种操作符。+、*都有单位元，若最右路径没有*，可以补上一个左孩子为1的节点；若没有+，可以补上一个左孩子为0的节点。这样保证了最右节点到根的距离恒为2，且树中有三个叶子，三个semantic values。

以上解释了三个semantic values可以刻画状态的原因。从左到右枚举各个位置上的符号，不难得到一个边枚举边求值的算法，枚举量为。常见优化技巧是meet-in-the-middle，即两边同时枚举到中间，把一边枚举的结果记录下来，另一边枚举到相遇时查表。用上这一技巧后，该算法很像packrat parser。倘若题目引入括号，那么LR(0)项集就含圈了，最右节点到根的距离就没有限制，3个semantic values就不够刻画状态。

注意相遇时要合并两边的部分结果。下面逐一考虑。

+相遇比较容易。假设左边部分的和为，那么从右边部分找和为的式子即可。

-相遇类似。

@相遇，合并时两边都得用到三个semantic values，与合并得到，难以计算，不存在有效的查表方法。因此我们不处理@相遇，放置并置符号后，交给递归调用的函数在之后相遇。若之后出现了+或-，那么相遇过程就延迟到那时进行；若没有出现，则在全式末尾进行。

*相遇，若像@那么不处理，考虑枚举量。设从右到左的有个操作符待枚举，预处理表的枚举量为。从左到右的枚举量为，每一项得在右边记录集合中查表。因为*、@两种符号都没处理相遇，还得考虑延迟相遇的情况数，为。若查表时间为常数，那么总的枚举量为。根据该式算得取时枚举量最小，考虑到查表的代价，实际取值应在与之间。

处理*相遇需要用到两个semantic values，把左边部分在最后一个加号处断开(-可以转化为+)，得到的形式，右边在第一个加号处断开，得到的形式，拼接得到。我们希望它等于，即。也就是说，对于右边两个semantic values 和所表示的直线，我们希望它经过点。

于是问题转化为：给出个点、根直线，对于每个点求经过它的直线。不妨设取。一种思路是借助spatial data structure。若能在的时间内计算，那么总的时间复杂度为。考虑把点组织成K-d tree，对每根线逐一查询，不小于，不优于不处理*相遇。更好的方法可能是把点和线批量处理。若为，则总的时间复杂度为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
typedef long long ll;
class Solution {
  string a;
  int n, nn, target;
  vector<multimap<ll, string>> e_plus, e_minus;
  vector<string> res;
  void backward(int k, string s, ll add, ll mul, ll last, ll ten) {
    if (k < nn) return;
    int x = a[k-1]-'0';
    ll ten2 = 10*ten, sum = add+mul*last;
    backward(k-1, string(1, a[k-1])+s, add, mul, last+ten2*x, ten2);
    if (ten == 1 || last >= ten) { // `last` has no leading zero
      backward(k-1, string(1, a[k-1])+'*'+s, add, mul*last, x, 1);
      backward(k-1, string(1, a[k-1])+'+'+s, sum, 1, x, 1);
      backward(k-1, string(1, a[k-1])+'-'+s, add-mul*last, 1, x, 1);
      e_plus[k].insert(make_pair(sum, s));
      e_minus[k].insert(make_pair(add-mul*last, s));
    }
  }
  void forward(int k, string s, ll add, ll mul, ll last) {
    ll sum = add+mul*last;
    if (k == n) {
      if (sum == target)
        res.push_back(s);
      return;
    }
    int x = a[k]-'0';
    if (last) // no leading zero
      forward(k+1, s+a[k], add, mul, last*10+x);
    forward(k+1, s+'*'+a[k], add, mul*last, x);
    if (k < nn) {
      forward(k+1, s+'+'+a[k], sum, 1, x);
      forward(k+1, s+'-'+a[k], sum, -1, x);
    } else {
      auto rg = e_plus[k].equal_range(target-sum);
      for (auto it = rg.first; it != rg.second; ++it)
        res.push_back(s+'+'+it->second);
      rg = e_minus[k].equal_range(target-sum);
      for (auto it = rg.first; it != rg.second; ++it)
        res.push_back(s+'-'+it->second);
    }
  }
public:
  vector<string> addOperators(string num, int target) {
    a = num;
    n = a.size();
    if (n) {
      nn = n/2; // 0 < nn < n
      this->target = target;
      e_plus.resize(n);
      e_minus.resize(n);
      backward(n-1, string(1, a[n-1]), 0, 1, a[n-1]-'0', 1);
      forward(1, string(1, a[0]), 0, 1, a[0]-'0');
    }
    return res;
  }
};