分治的思想：1分2治3合并解
这题最难的就是要想到 在运算符上分开。分治和递归是双胞胎啊！想不到啊想不到，不能再放纵自己了，眼睛干涩。
vector<int> diffWaysToCompute(string input) {
vector<int> result;
for (int i = 0; i < input.size(); i++) {
char ch = input[i];
if (ch == ‘+‘ || ch == ‘-‘ || ch == ‘*‘) {
vector<int> lv = diffWaysToCompute(input.substr(0, i));
vector<int> rv = diffWaysToCompute(input.substr(i+1));
for (auto x : lv) {
for (auto y : rv) {
if (ch == ‘+‘) {
result.push_back(x+y);
} else if (ch == ‘*‘) {
result.push_back(x*y);
} else if (ch == ‘-‘) {
result.push_back(x-y);
}
}
}
}
}
if (result.empty()) {
result.push_back(atoi(input.c_str()));
}
return result;
vector<int> diffWaysToCompute(string input) {
vector<int> ans;
bool pureNum=true;
for (int i=0; i<input.length(); i++)
if (input[i]<‘0‘ || input[i]>‘9‘) {
pureNum=false;
vector<int> L=diffWaysToCompute(input.substr(0, i)), R=diffWaysToCompute(input.substr(i+1, input.length()-i-1));
for (auto l : L)
for (auto r : R)
if (c==‘+‘) ans.push_back(l+r);
else if (c==‘-‘) ans.push_back(l-r);
else if (c==‘*‘) ans.push_back(l*r);
}
if (pureNum)
ans.push_back(atoi(input.c_str()));
return ans;
}
这是一个二叉树啊，递归就是解决二叉树的。应该形成固定思维啊暂时。
LeetCode() Different Ways to Add Parentheses
原文：http://www.cnblogs.com/yanqi110/p/4981742.html