# 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"
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
# Solution
Approach 1: recursion.
# Code (Python)
Approach 1:
class Solution(object):
def diffWaysToCompute(self, input):
"""
:type input: str
:rtype: List[int]
"""
if input.isdigit():
return [int(input)]
result = []
for i, char in enumerate(input):
if char in '+-*':
left = self.diffWaysToCompute(input[:i])
right = self.diffWaysToCompute(input[i+1:])
for l in left:
for r in right:
result.append(self.calc(l, r, char))
return sorted(result)
def calc(self, l, r, char):
return {'+': lambda a,b: a+b, '-':lambda a,b: a-b, '*':lambda a,b: a*b}[char](l, r)
# Code (C++)
Approach 1:
class Solution {
private:
unordered_map<string,vector<int>> tempVals;
int doOp(int num1, int num2, char op) {
switch (op)
{
case '+' : return num1 + num2;
case '-' : return num1 - num2;
case '*' : return num1 * num2;
}
return 0;
}
public:
vector<int> diffWaysToCompute(string input) {
if (tempVals.find(input) != tempVals.end())
return tempVals[input];
vector<int> res;
for (int i = 0; i < input.size(); ++i)
{
if (!isdigit(input[i]))
{
vector<int> left = diffWaysToCompute(input.substr(0, i));
vector<int> right = diffWaysToCompute(input.substr(i+1, input.size()-i-1));
for (int j = 0; j < left.size(); ++j)
{
for (int k = 0; k < right.size(); ++k)
{
res.push_back(doOp(left[j], right[k], input[i]));
}
}
}
}
if (res.size() == 0)
res.push_back(stoi(input));
return res;
}
};