[leetcode]241. Different Ways to Add Parentheses
Analysis
ummmm—— [每天刷题并不难。。。其实已经很多天没刷了]
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，遇到运算符就把input分成两部分，然后再分别遍历两个部分。其实这题就是让我们忽略运算符的优先级，计算出式子的所有可能结果。
Implement
class Solution {
public
:
vector
<int> diffWaysToCompute
(string
input) {
vector
<int> res
;
int len = input.size
();
for(int i
=0; i
<len; 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(auto l
:left
){
for(auto r
:right
){
if(input[i
] == '+')
res
.push_back
(l
+r
);
else if(input[i
] == '-')
res
.push_back
(l
-r
);
else if(input[i
] == '*')
res
.push_back
(l
*r
);
}
}
}
}
if(res
.size
() == 0)
res
.push_back
(atoi
(input.c_str
()));
return res
;
}
};
