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 *. Difficulty: Medium
题目的意思是，获取一个算式，找出各种不同运算顺序下的结果。 这种情况下，一个运算符相当于一个节点，将其算式分为两个子树。所以将字符串形式的算式遍历一次，遇到有“+”，“-”，“*”运算符就将算式divide。以运算符为中点将算式分为left，right两个子串，用vector容器存储。left，right子串再分别递归调用diffWaysToCompute函数，将自身再divide。当问题分割到只剩下一个运算符连接两个数字的最小问题时，计算出结果。然后再逐层将左右结果conquer，存储到result中。 本题代码如下：
class Solution { public: vector<int> diffWaysToCompute(string input) { vector<int> result; int len = input.size(); for(int i = 0; i < len; i++){ char op = input[i]; if(op == '+' || op == '-' || op == '*'){ vector<int> left = diffWaysToCompute(input.substr(0, i)); vector<int> right = diffWaysToCompute(input.substr(i + 1, len - 1)); for(int j = 0; j < left.size(); j++){ for(int k = 0; k < right.size(); k++){ if(op == '+'){ result.push_back(left[j] + right[k]); } if(op == '-'){ result.push_back(left[j] - right[k]); } if(op == '*'){ result.push_back(left[j] * right[k]); } } } } } if(result.empty()) result.push_back(atoi(input.c_str())); return result; } };