题意简述：给定一个数字串和一个目标值，允许在数字串中任意两个相邻数字之间插入+、-和*来组成表达式，求出所有这样的表达式，表达式求出的值恰好等于目标值。 输入：一个只由数字组成的字符串num，一个整数target。 输出：所有计算值为目标值的表达式。 示例：输入为（”105”,5），输出为[“1*0+5”,”10-5”]
题解： 这应该是条搜索题，搜索所有可能的表达式并分别计算结果，储存所有结果等于目标值的表达式。 要怎么搜索呢？首先想到的是按运算符来搜索，实际上数字之间不插入运算符也是一种运算，我把它称之为“合并”（以符号”|”表示），例如示例中的10-5可以看成1|0-5，而且合并的优先级比乘法更高。因此我想到的一种搜索方法是优先级高到低的枚举，以”105”为例的搜索过程如下图（因为加法与减法的优先级相同，因此这里略去对减法的搜索）： 
后来在开始构思实现细节的时候，发现了两个因为搜索顺序而引起的比较大的问题：
因为对运算符的搜索并没有严格按照某个方向的顺序进行（搜索是按优先级进行的），导致在表达式右边的运算符可能先被搜索，将产生一些中间结果。例如”12345”经过两次搜索变成”1 2|3 4|5”，23和45并没有出现在原表达式中，需要为这些中间结果储存运算符串，表示怎么通过运算得到这些中间结果，每一层的搜索都需要将所有中间结果及其运算符串向下传递，空间规模的增长不可控制。“合并”运算不好定义，因为会产生中间结果，中间结果的位数不确定，因此下不了代数定义，只能用字符串拼接实现。空间问题相对来说更加严重，因此需要优先考虑解决方案，既然问题出自可能先搜索后面的运算符，那么我可以令运算符的搜索严格从左到右，这样运算符串也是自左向右增加的，不会突然出现在中间。但是每一层的搜索的运算符串仍然需要向下传递？空间问题没有解决？一旦我将遍历定在自左向右，我就可以使用深度优先搜索。这时候在同一次递归中，所有进入下层递归的运算符串具有相同的前缀，向下的搜索不会改变之前的运算符，因此整个深度优先搜索过程只需要共用一个运算符串就可以。 另外使用深度优先搜索恰好也解决了第二个问题，从左到右搜索，|运算的右运算数永远是一位数，所以可以定义a|b=a*10+b。 于是问题只剩下，如何在从左到右搜索的过程中准确地算出表达式的值。毕竟，总不能把2+3*5算成(2+3)*5的吧。
解决方案是，引入累计器概念来保证运算完全按优先级进行。
4种运算共有3个优先级（|最高，*次之，+-最低），为每个优先级单独设置一个累计器，累计器的值实质是运算的左运算数。在进行一个运算时，要先把更高优先级的运算结算完成，再把更高优先级的累计器的值参与到运算中（也即先进行高优先级运算再进行低优先级运算），最后结果存放在该运算的累计器中，更高优先级的累计器清空。例如，在搜索到*号时，要先把之前出现的|运算算出结果，跟存放在乘法累计器的值相乘，此时乘法累计器的值才是这个乘法真正的左运算数。乘法运算的累计器清空默认值为1，这是因为乘法的单位元是1，其余两个累计器的清空默认值是0。深度优先搜索中累计器的操作： 记|运算的累计器值为ac，乘法的累计器值为am，加减法的累计器值为as，当前搜索位的数字是k。（k=num[index]） 则在任意时刻，搜索得到的表达式的值为(ac*10+k)*am+as。
|运算：由于是最高优先级的运算，因此只需要修改ac。需要注意不允许1+0|9这种情况（数的最高位不能为0） (ac, am, as) -> (ac*10+k, am, as)乘法：进行乘法之前，需要先把之前出现的|运算完成（即ac|k），再将结果与am相乘。如果表达式从头到尾都没有|运算呢？如果是这样的话，ac=0，ac*10+k=k，则am=k*am，这就相当于只做了乘法，这与实际是一致的。 (ac, am, as) -> (0, (ac*10+k)*am, as)加法：进行加法之前，需要先把之前出现的|运算和乘法都完成（即(ac|k)*am），再将结果与as相加。如果表达式只有加减法？那么ac=0，am=1，as=（ac*10+k）*am+as = k*am+as=k+as，与只做加法一致。 (ac, am, as) -> (0, 1, (ac*10+k)*am+as)减法：与加法的操作大致相同，唯一的不同是需要将乘法累计器设置为-1，这样在之后的运算中(ac*10+k)*am+as就相当于as-|(ac*10+k)*am|。（这里的|x|是绝对值） (ac, am, as) -> (0, -1, (ac*10+k)*am+as)以”125340”在某一搜索过程中得到125+3*40为例： 
那么表达式的值是(4*10+0)*3+125=40*3+125=245
现在能够准确算出表达式的值，那么剩下的步骤是跟目标值比较，如果一致，则将原来的数字串num(“125340”)与搜索得到的符号串(“||+*|”)合并得到表达式(“125+3*40”)，所有的”|”都不输出。
实现的细节如下：
class Solution {PRivate: long long _target; string _num; // ac : accumlator of combine // am : accumlator of multiply // as : accumlator of sum&minus void recur(char *ops, int index, long long ac, long long am, long long as, vector<string>& result) { int k = _num[index] - '0'; if(index == _num.size() - 1) { if((ac*10+k)*am+as == _target) { string s; for(int i = 0;i<_num.size()-1;i++) { s.push_back(_num[i]); if(ops[i] != '|') s.push_back(ops[i]); } s.push_back(_num[_num.size()-1]); result.push_back(s); } return; } if(!(ac == 0 && k == 0)) { ops[index] = '|'; recur(ops, index+1, ac*10+k, am, as, result); } ops[index] = '*'; recur(ops, index+1, 0, (ac*10+k)*am, as, result); ops[index] = '+'; recur(ops, index+1, 0, 1, (ac*10+k)*am+as, result); ops[index] = '-'; recur(ops, index+1, 0, -1, (ac*10+k)*am+as, result); }public: vector<string> addOperators(string num, int target) { _target = target; _num = num; vector<string> result; if(num.size() == 0) return result; char ops[num.size()]; recur(ops, 0, 0, 1, 0, result); return result; }};新闻热点
疑难解答
