|
| 1 | +# Time: O(m + n^3 * logn) |
| 2 | +# Space: O(m + n) |
| 3 | + |
| 4 | +class Poly(collections.Counter): |
| 5 | + def __add__(self, other): |
| 6 | + self.update(other) |
| 7 | + return self |
| 8 | + |
| 9 | + def __sub__(self, other): |
| 10 | + self.update({k: -v for k, v in other.items()}) |
| 11 | + return self |
| 12 | + |
| 13 | + def __mul__(self, other): |
| 14 | + result = Poly() |
| 15 | + for k1, v1 in self.items(): |
| 16 | + for k2, v2 in other.items(): |
| 17 | + result.update({tuple(sorted(k1+k2)): v1*v2}) |
| 18 | + return result |
| 19 | + |
| 20 | + def evaluate(self, lookup): |
| 21 | + result = Poly() |
| 22 | + for k, c in self.items(): |
| 23 | + poly = [] |
| 24 | + for token in k: |
| 25 | + if token in lookup: |
| 26 | + c *= lookup[token] |
| 27 | + else: |
| 28 | + poly.append(token) |
| 29 | + result[tuple(poly)] += c |
| 30 | + return result |
| 31 | + |
| 32 | + def to_list(self): |
| 33 | + return ["*".join((str(v),) + k) \ |
| 34 | + for k, v in sorted(self.items(), key=lambda(k, v): (-len(k), k, v)) \ |
| 35 | + if v] |
| 36 | + |
| 37 | + |
| 38 | +class Solution(object): |
| 39 | + def basicCalculatorIV(self, expression, evalvars, evalints): |
| 40 | + """ |
| 41 | + :type expression: str |
| 42 | + :type evalvars: List[str] |
| 43 | + :type evalints: List[int] |
| 44 | + :rtype: List[str] |
| 45 | + """ |
| 46 | + lookup = dict(itertools.izip(evalvars, evalints)) |
| 47 | + |
| 48 | + def do_operator(left, right, operator): |
| 49 | + if operator == '+': return left + right |
| 50 | + if operator == '-': return left - right |
| 51 | + if operator == '*': return left * right |
| 52 | + raise |
| 53 | + |
| 54 | + def make_operand(expr): |
| 55 | + result = Poly() |
| 56 | + if expr.isdigit(): |
| 57 | + result.update({(): int(expr)}) |
| 58 | + else: |
| 59 | + result[(expr,)] += 1 |
| 60 | + return result |
| 61 | + |
| 62 | + def parse(expr): |
| 63 | + operands, operators = [], [] |
| 64 | + i = 0 |
| 65 | + while i < len(expr): |
| 66 | + if expr[i] == '(': |
| 67 | + cnt = 0 |
| 68 | + for j in xrange(i, len(expr)): |
| 69 | + if expr[j] == '(': cnt += 1 |
| 70 | + if expr[j] == ')': cnt -= 1 |
| 71 | + if cnt == 0: break |
| 72 | + operands.append(parse(expr[i+1:j])) |
| 73 | + i = j |
| 74 | + elif expr[i].isalnum(): |
| 75 | + for j in xrange(i, len(expr)): |
| 76 | + if expr[j] == ' ': |
| 77 | + operands.append(make_operand(expr[i:j])) |
| 78 | + break |
| 79 | + else: |
| 80 | + operands.append(make_operand(expr[i:])) |
| 81 | + i = j |
| 82 | + elif expr[i] in '+-*': |
| 83 | + operators.append(expr[i]) |
| 84 | + i += 1 |
| 85 | + |
| 86 | + for i in reversed(xrange(len(operators))): |
| 87 | + if operators[i] == '*': |
| 88 | + operands[i] = do_operator(operands[i], operands.pop(i+1), \ |
| 89 | + operators.pop(i)) |
| 90 | + |
| 91 | + if not operands: return Poly() |
| 92 | + result = operands[0] |
| 93 | + for i, operator in enumerate(operators, 1): |
| 94 | + result = do_operator(result, operands[i], operator) |
| 95 | + return result |
| 96 | + |
| 97 | + return parse(expression).evaluate(lookup).to_list() |
0 commit comments