题目:
- 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 *.
- Example 1:
- Input: "2-1-1"
- Output: [0, 2]
- Explanation:
- ((2-1)-1) = 0
- (2-(1-1)) = 2
- Example 2:
- Input: "2*3-4*5"
- Output: [-34, -14, -10, -10, 10]
- Explanation:
- (2*(3-(4*5))) = -34
- ((2*3)-(4*5)) = -14
- ((2*(3-4))*5) = -10
- (2*((3-4)*5)) = -10
- (((2*3)-4)*5) = 10
分析:
给定一个含有数字和运算符的字符串, 为表达式添加括号, 改变其运算优先级以求出不同的结果. 你需要给出所有可能的组合的结果. 有效的运算符号包含 +, - 以及 * .
以运算符号为界限来划分出左右两个子串, 继续递归执行子串, 直到只有一个元素为止.
左右两个子串的结果存进数组中, 对其中的元素遍历组合得到结果.
diff(2*3-4*5) = { diff(2) * diff(3-4*5) } + { diff(2*3) - diff(4*5) } + { diff(2*3-4) * diff(5) }
其中 diff(3-4*5) = {diff(3) - diff(4*5),diff(3-4) * diff(5)}={3-20,-1*5}={-17,-5}
diff(2*3-4) = {diff(2) * diff(3-4),diff(2*3) - diff(4)} = {2*-1,6-4} = {-2,2}
所以 diff(2*3-4*5) = {2*{-17,-5}}+{6-20}+{{-2,2}*5}={-34,-10}+{-14}+{-10,10}={-34,-10,-14,-10,10}
程序:
- class Solution {
- public:
- vector<int> diffWaysToCompute(string input) {
- vector<int> res;
- for(int i = 0; i <input.size(); ++i){
- if(input[i] == '+' || input[i] == '-' || input[i] == '*'){
- vector<int> l = diffWaysToCompute(input.substr(0, i));
- vector<int> r = diffWaysToCompute(input.substr(i+1, input.size()-i));
- for(auto p:l)
- for(auto q:r){
- if(input[i] == '+')
- res.push_back(p+q);
- if(input[i] == '-')
- res.push_back(p-q);
- if(input[i] == '*')
- res.push_back(p*q);
- }
- }
- }
- if(res.empty())
- res.push_back(stoi(input));
- return res;
- }
- };
来源: http://www.bubuko.com/infodetail-3066422.html