基本计算器 IV

题解使用了一种多项式处理方法，通过自定义的Poly类（基于collections.Counter），来表示和操作多项式。每个Poly实例表示一个多项式，其中键是变量组合的元组，值是相应的系数。 1. __add__ 和 __sub__ 方法重载了加法和减法运算符来合并和减去多项式。 2. __mul__ 方法通过嵌套循环计算两个多项式的乘积，组合项的所有可能的变量组合，并更新结果多项式。 3. evaluate 方法通过给定的变量映射替换变量值，并合并多项式中相同的项。 4. to_list 方法用于将多项式转换为规定格式的字符串列表，按照项的次数（降序）、变量的字典序排列。 解析表达式的过程(parse)使用递归来处理括号和操作符，生成相应的多项式对象。该方法首先分离出各个组成部分（数字、变量或括号内的表达式），并根据运算符适当组合它们。

时间复杂度: O(n + m^2)，其中n是表达式的长度，m是操作数中项的数量

空间复杂度: O(m^2)

class Poly(collections.Counter):
    # 初始化多项式，继承Counter以方便统计和操作
    def __add__(self, other):
        # 加法操作，更新当前多项式的每个项
        self.update(other)
        return self

    def __sub__(self, other):
        # 减法操作，更新当前多项式，为other的每个项系数取反
        self.update({k: -v for k, v in other.items()})
        return self

    def __mul__(self, other):
        # 乘法操作，计算当前多项式与另一多项式的所有项的乘积
        ans = Poly()
        for k1, v1 in self.items():
            for k2, v2 in other.items():
                ans.update({tuple(sorted(k1 + k2)): v1 * v2})
        return ans

    def evaluate(self, evalmap):
        # 计算多项式的值，替换变量为具体数值
        ans = Poly()
        for k, c in self.items():
            free = []
            for token in k:
                if token in evalmap:
                    c *= evalmap[token]
                else:
                    free.append(token)
            ans[tuple(free)] += c
        return ans

    def to_list(self):
        # 转换多项式为规定格式的字符串列表
        p = sorted(self.items(), key=lambda kv: (-len(kv[0]), kv[0], kv[1]))
        return ['*'.join((str(v),) + k) for k, v in p if v]

class Solution(object):
    def basicCalculatorIV(self, expression, evalvars, evalints):
        evalmap = dict(zip(evalvars, evalints))

        def combine(left, right, symbol):
            # 根据符号执行相应的多项式运算
            if symbol == '+': return left + right
            if symbol == '-': return left - right
            if symbol == '*': return left * right
            raise

        def make(expr):
            # 生成多项式对象，将表达式转换为多项式
            ans = Poly()
            if expr.isdigit():
                ans.update({(): int(expr)})
            else:
                ans[(expr,)] += 1
            return ans

        def parse(expr):
            # 解析表达式，处理括号和操作符，递归构造多项式
            bucket = []
            symbols = []
            i = 0
            while i < len(expr):
                if expr[i] == '(': 
                    bal = 0
                    for j in range(i, len(expr)):
                        if expr[j] == '(': bal += 1
                        if expr[j] == ')': bal -= 1
                        if bal == 0: break
                    bucket.append(parse(expr[i+1:j]))
                    i = j
                elif expr[i].isalnum():
                    for j in range(i, len(expr)):
                        if expr[j] == ' ':
                            bucket.append(make(expr[i:j]))
                            break
                    else:
                        bucket.append(make(expr[i:]))
                    i = j
                elif expr[i] in '+-*':
                    symbols.append(expr[i])
                i += 1

            for i in range(len(symbols) - 1, -1, -1):
                if symbols[i] == '*':
                    bucket[i] = combine(bucket[i], bucket.pop(i+1),
                                        symbols.pop(i))

            if not bucket: return Poly()
            ans = bucket[0]
            for i, symbol in enumerate(symbols, 1):
                ans = combine(ans, bucket[i], symbol)

            return ans

        P = parse(expression).evaluate(evalmap)
        return P.to_list()