FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

LeetCode-Solutions/Python/basic-calculator-iv.py at master · pythonpeixun/LeetCode-Solutions · GitHub

119 lines (105 loc) · 3.64 KB

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

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

# Time: +: O(d * t), t is the number of terms,

# d is the average degree of terms

# -: O(d * t)

# *: O(d * t^2)

# eval: O(d * t)

# to_list: O(d * tlogt)

# Space: O(e + d * t), e is the number of evalvars

import collections

import itertools

class Poly(collections.Counter):

def __init__(self, expr=None):

if expr is None:

return

if expr.isdigit():

self.update({(): int(expr)})

else:

self[(expr,)] += 1

def __add__(self, other):

self.update(other)

return self

def __sub__(self, other):

self.update({k: -v for k, v in other.items()})

return self

def __mul__(self, other):

def merge(k1, k2):

result = []

i, j = 0, 0

while i != len(k1) or j != len(k2):

if j == len(k2):

result.append(k1[i])

i += 1

elif i == len(k1):

result.append(k2[j])

j += 1

elif k1[i] < k2[j]:

result.append(k1[i])

i += 1

else:

result.append(k2[j])

j += 1

return result

result = Poly()

for k1, v1 in self.items():

for k2, v2 in other.items():

result.update({tuple(merge(k1, k2)): v1*v2})

return result

def eval(self, lookup):

result = Poly()

for polies, c in self.items():

key = []

for var in polies:

if var in lookup:

c *= lookup[var]

else:

key.append(var)

result[tuple(key)] += c

return result

def to_list(self):

return ["*".join((str(v),) + k)

for k, v in sorted(self.items(),

key=lambda x: (-len(x[0]), x[0]))

if v]

class Solution(object):

def basicCalculatorIV(self, expression, evalvars, evalints):

"""

:type expression: str

:type evalvars: List[str]

:type evalints: List[int]

:rtype: List[str]

"""

def compute(operands, operators):

left, right = operands.pop(), operands.pop()

op = operators.pop()

if op == '+':

operands.append(left + right)

elif op == '-':

operands.append(left - right)

elif op == '*':

operands.append(left * right)

def parse(s):

if not s:

return Poly()

operands, operators = [], []

operand = ""

for i in reversed(xrange(len(s))):

if s[i].isalnum():

operand += s[i]

if i == 0 or not s[i-1].isalnum():

operands.append(Poly(operand[::-1]))

operand = ""

elif s[i] == ')' or s[i] == '*':

operators.append(s[i])

elif s[i] == '+' or s[i] == '-':

while operators and operators[-1] == '*':

compute(operands, operators)

operators.append(s[i])

elif s[i] == '(':

while operators[-1] != ')':

compute(operands, operators)

operators.pop()

while operators:

compute(operands, operators)

return operands[-1]

lookup = dict(itertools.izip(evalvars, evalints))

return parse(expression).eval(lookup).to_list()

Back | FazBrowse Home | New Git URL