Google/WaystoAddParentheses.py at master · rmathure/Google · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
__author__ = 'rohanmathure'

import unittest

'''
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".

'''

class Solution(object):
    def __init__(self):
        self.operators = set(['+','-','*'])

    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        operator_list = list()
        num_list = list()
        temp_str = str()
        for char in input:
            if char in self.operators:
                num_list.append(temp_str)
                temp_str = ""
                operator_list.append(char)
            else:
                temp_str += char
        if len(temp_str) > 0:
            num_list.append(temp_str)
        return self.parseInput(num_list, operator_list)

    def compute(self, a, b, op):
        if op == '+':
            return int(a)+int(b)
        elif op == '-':
            return int(a)-int(b)
        elif op == '*':
            return int(a)*int(b)

    def parseInput(self, num_list, operator_list):
        output = list()
        if len(num_list) == 0:
            return []
        elif len(num_list) == 1:
            return [int(num_list[0])]
        elif len(num_list) == 2:
            return [self.compute(num_list[0], num_list[1], operator_list[0])]
        else:
            output = map(lambda x: self.compute(num_list[0], x, operator_list[0])
                                ,self.parseInput(num_list[1:], operator_list[1:]))
            output.extend(map(
                lambda x: self.compute(self.compute(num_list[0], num_list[1], operator_list[0]), x, operator_list[1])
                                ,self.parseInput(num_list[2:], operator_list[2:])))
            if len(num_list) > 3:
                output.extend(map(lambda x: self.compute(x, num_list[-1], operator_list[-1]) ,
                                  self.parseInput(num_list[:-1], operator_list[:-1])))
            return output


class TestDifferentWays(unittest.TestCase):
    def test_base(self):
        self.assertEqual(Solution().diffWaysToCompute("0"), [0])

    def test_two_num(self):
        self.assertEqual(Solution().diffWaysToCompute("1+0"), [1])

    def test_multiple(self):
        self.assertEqual(Solution().diffWaysToCompute("15-7*6+24"), [-195,-51,-3,72,240])