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.

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

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

考虑题目要求的文法：

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

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

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

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

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

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

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

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

-相遇类似。

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

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

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

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