Different Ways to Add Parentheses
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 *.
这道题主要思想是Divide and Conquer 分治法
对于一个表达式 a - b, a与b均为表达式，计算a - b的结果 我们需要先知道a的结果与b的结果。对于知道加parentheses的题，只要对表达中的每一个运算符都做这样的操作并递归，就可以得出所有可能结果，希望下面的例子可以帮助理解
2 * 3 - 4 * 5
/ \
2 * (3 - 4 * 5) ...
/ \
(3 - 4 ) * 5 3 - (4 * 5)
/ \
3 4
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> result;
for (int i = 0; i < input.size(); i++) {
char c = input[i];
if (c == '+' || c == '-' || c == '*') {
auto result1 = diffWaysToCompute(input.substr(0, i));
auto result2 = diffWaysToCompute(input.substr(i + 1));
for (int r1: result1) {
for (int r2: result2) {
if (c == '+')
result.push_back(r1 + r2);
else if (c == '-')
result.push_back(r1 - r2);
else
result.push_back(r1 * r2);
}
}
}
}
if (result.empty())
result.push_back(atoi(input.c_str()));
return result;
}
};
