_241_different_ways_to_add_parentheses.py 文件源码

def diffWaysToCompute(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        tokens = re.split('(\D)', s)            # magical regular expression
        nums = map(int, tokens[::2])            # nums: an array, ops: a method (operator.xxx)
        ops = map({'+': operator.add, '-': operator.sub, '*': operator.mul}.get, tokens[1::2])
        def build(lo, hi):                      # top-down method
           if lo == hi:
               return [nums[lo]]
           return [ops[i](a, b)
                   for i in xrange(lo, hi)
                   for a in build(lo, i)
                   for b in build(i + 1, hi)]
        return build(0, len(nums)-1)