Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
解题思路：首先遍历input字符串，每遇到一个运算符，就分别计算该运算符之前和之后两部分的可能值res_right和res_left,然后两层循环这两个vector，将运算结果放入res中。最后要记得讨论若res为空的情况，即input中只有一个数字，这时直接将该数字加入res（ret.push_back(atoi(input.c_str()));）该方法也是string类转化为int/long类的一种常用方法。
class Solution { public: vector<int> diffWaysToCompute(string input) { vector<int> ret; for(int i = 0; i < input.size(); i ++) { if(input[i] == '+' || input[i] == '-' || input[i] == '*') { vector<int> left = diffWaysToCompute(input.substr(0, i)); vector<int> right = diffWaysToCompute(input.substr(i+1)); for(int j = 0; j < left.size(); j ++) { for(int k = 0; k < right.size(); k ++) { if(input[i] == '+') ret.push_back(left[j] + right[k]); else if(input[i] == '-') ret.push_back(left[j] - right[k]); else ret.push_back(left[j] * right[k]); } } } } if(ret.empty()) ret.push_back(atoi(input.c_str())); return ret; } };总结：通过计算可知该方法的复杂度为O(n*3)，主要难点就是运用到递归使得代码简洁（直接算出左右两部分的子vector），，还有要注意的地方就是递归的递归的最后情况，只有一个数字了，要最后讨论，这是特变要注意的一点。