Solution.py

class Solution(object):
    def diffWaysToCompute(self, input):
        memo = {}
        return self.buildTrees(input, memo)

    def buildTrees(self, s, memo):
        if s in memo:
            return memo[s]
        response = []
        isOperand = True
        for i in xrange(len(s)):
            if s[i] in ['*', '+', '-']:
                isOperand = False
                left = self.buildTrees(s[:i], memo)
                right = self.buildTrees(s[i + 1:], memo)
                for left_tree in left:
                    for right_tree in right:
                        value = {'-': left_tree - right_tree,
                                 '+': left_tree + right_tree,
                                 '*': left_tree * right_tree}[s[i]]
                        response.append(value)
        if isOperand:
            return [int(s)]
        else:
            memo[s] = response
            return response