241 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 *
.
Example 1
Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]
Example 2
Input: "2*3-4*5"
(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
Output: [-34, -14, -10, -10, 10]
Solution
class Solution {
public:
vector<int> calculate(vector<int> nums, vector<char> signs, int s1, int s2) {
vector<int> res;
if ( s1 > s2 ) {
res.push_back(nums[s1]);
return res;
}
for ( int i = s1; i <= s2; i++ ) {
vector<int> res1 = calculate(nums, signs, s1, i-1);
vector<int> res2 = calculate(nums, signs, i+1, s2);
int n1 = res1.size(), n2 = res2.size();
for ( int i1 = 0; i1 <= n1-1; i1++) {
for ( int i2 = 0; i2 <= n2-1; i2++ ) {
if ( signs[i] == '+' ) res.push_back(res1[i1] + res2[i2]);
if ( signs[i] == '-' ) res.push_back(res1[i1] - res2[i2]);
if ( signs[i] == '*' ) res.push_back(res1[i1] * res2[i2]);
}
}
}
return res;
}
vector<int> diffWaysToCompute(string input) {
int n = input.size();
vector<int> res;
if ( n == 0 ) return res;
vector<int> nums;
vector<char> signs;
string tmp = "";
for ( int i = 0; i <= n-1; i++ ) {
if ( input[i] >= '0' and input[i] <= '9' ) tmp += input[i];
else {
nums.push_back(stoi(tmp));
tmp = "";
signs.push_back(input[i]);
}
}
nums.push_back(stoi(tmp));
int ns = signs.size();
res = calculate(nums, signs, 0, ns-1);
return res;
}
};
Notes
Similar to "Catlan Number" problem.