**Solution**

**Different Ways to Add Parentheses** https://leetcode.com/problems/different-ways-to-add-parentheses/

**Divide and Conquer Algorithm**

- Split the input at an operator. Evaluate the left half, evaluate the right half, and then merge the two.
- Base condition is when input has no operator, simply return the integer equivalent of the input.

```
class Solution(object):
def diffWaysToCompute(self, input):
return self.helper(input)
def merge(self, left, right, x, result):
eval_method = {"+": lambda x,y: x+y, "-": lambda x,y: x-y, "*": lambda x,y: x*y}
for a in left:
for b in right:
result.append(eval_method[x](a, b))
return
def helper(self, expr):
"""
:type input: str
:rtype: List[int]
"""
result = []
if "+" not in expr and "-" not in expr and "*" not in expr:
return [int(expr)]
for i, x in enumerate(expr):
if x in ("+", "-", "*"):
left, right = self.helper(expr[0:i]), self.helper(expr[i+1:])
self.merge(left, right, x, result)
return result
```