@@ -0,0 +1,3185 @@
+# Time:  O(m + n%5E3 * logn)%0A# Space: O(m + n)%0A%0Aclass Poly(collections.Counter):%0A    def __add__(self, other):%0A        self.update(other)%0A        return self%0A%0A    def __sub__(self, other):%0A        self.update(%7Bk: -v for k, v in other.items()%7D)%0A        return self%0A%0A    def __mul__(self, other):%0A        result = Poly()%0A        for k1, v1 in self.items():%0A            for k2, v2 in other.items():%0A                result.update(%7Btuple(sorted(k1+k2)): v1*v2%7D)%0A        return result%0A%0A    def evaluate(self, lookup):%0A        result = Poly()%0A        for k, c in self.items():%0A            poly = %5B%5D%0A            for token in k:%0A                if token in lookup:%0A                    c *= lookup%5Btoken%5D%0A                else:%0A                    poly.append(token)%0A            result%5Btuple(poly)%5D += c%0A        return result%0A%0A    def to_list(self):%0A        return %5B%22*%22.join((str(v),) + k) %5C%0A                for k, v in sorted(self.items(), key=lambda(k, v): (-len(k), k, v)) %5C%0A                if v%5D%0A    %0A    %0Aclass Solution(object):%0A    def basicCalculatorIV(self, expression, evalvars, evalints):%0A        %22%22%22%0A        :type expression: str%0A        :type evalvars: List%5Bstr%5D%0A        :type evalints: List%5Bint%5D%0A        :rtype: List%5Bstr%5D%0A        %22%22%22%0A        lookup = dict(itertools.izip(evalvars, evalints))%0A%0A        def do_operator(left, right, operator):%0A            if operator == '+': return left + right%0A            if operator == '-': return left - right%0A            if operator == '*': return left * right%0A            raise%0A%0A        def make_operand(expr):%0A            result = Poly()%0A            if expr.isdigit():%0A                result.update(%7B(): int(expr)%7D)%0A            else:%0A                result%5B(expr,)%5D += 1%0A            return result%0A%0A        def parse(expr):%0A            operands, operators = %5B%5D, %5B%5D%0A            i = 0%0A            while i %3C len(expr):%0A                if expr%5Bi%5D == '(':%0A                    cnt = 0%0A                    for j in xrange(i, len(expr)):%0A                        if expr%5Bj%5D == '(': cnt += 1%0A                        if expr%5Bj%5D == ')': cnt -= 1%0A                        if cnt == 0: break%0A                    operands.append(parse(expr%5Bi+1:j%5D))%0A                    i = j%0A                elif expr%5Bi%5D.isalnum():%0A                    for j in xrange(i, len(expr)):%0A                        if expr%5Bj%5D == ' ':%0A                            operands.append(make_operand(expr%5Bi:j%5D))%0A                            break%0A                    else:%0A                        operands.append(make_operand(expr%5Bi:%5D))%0A                    i = j%0A                elif expr%5Bi%5D in '+-*':%0A                    operators.append(expr%5Bi%5D)%0A                i += 1%0A%0A            for i in reversed(xrange(len(operators))):%0A                if operators%5Bi%5D == '*':%0A                    operands%5Bi%5D = do_operator(operands%5Bi%5D, operands.pop(i+1), %5C%0A                                              operators.pop(i))%0A%0A            if not operands: return Poly()%0A            result = operands%5B0%5D%0A            for i, operator in enumerate(operators, 1):%0A                result = do_operator(result, operands%5Bi%5D, operator)%0A            return result%0A%0A        return parse(expression).evaluate(lookup).to_list()%0A

Create basic-calculator-iv.py