1.题目基本信息

1.1.题目描述

给定一个表达式如 expression = "e + 8 - a + 5" 和一个求值映射，如 {"e": 1}（给定的形式为 evalvars = ["e"] 和 evalints = [1]），返回表示简化表达式的标记列表，例如 ["-1*a","14"]

• 表达式交替使用块和符号，每个块和符号之间有一个空格。

• 块要么是括号中的表达式，要么是变量，要么是非负整数。

• 变量是一个由小写字母组成的字符串（不包括数字）。请注意，变量可以是多个字母，并注意变量从不具有像 "2x" 或 "-x" 这样的前导系数或一元运算符 。

表达式按通常顺序进行求值：先是括号，然后求乘法，再计算加法和减法。

• 例如，expression = "1 + 2 * 3" 的答案是 ["7"]。

输出格式如下：

• 对于系数非零的每个自变量项，我们按字典排序的顺序将自变量写在一个项中。

  • 例如，我们永远不会写像 “bac” 这样的项，只写 “abc”。

• 项的次数等于被乘的自变量的数目，并计算重复项。我们先写出答案的最大次数项，用字典顺序打破关系，此时忽略词的前导系数。

  • 例如，"aab*c" 的次数为 4。

• 项的前导系数直接放在左边，用星号将它与变量分隔开(如果存在的话)。前导系数 1 仍然要打印出来。

• 格式良好的一个示例答案是 ["-2aaa", "3aab", "3bb", "4a", "5c", "-6"] 。

• 系数为 0 的项（包括常数项）不包括在内。

  • 例如，“0” 的表达式输出为 [] 。

注意：你可以假设给定的表达式均有效。所有中间结果都在区间 [-231, 231 - 1] 内。

1.2.题目地址

https://leetcode.cn/problems/basic-calculator-iv/description/

2.解题方法

2.1.解题思路

多项式类+递归+双栈

3.解题代码

python3代码

from collections import Counter

# 构建多项式类。这里采用"变量名元组->数目"的方式来存储多项式；b比如-1*a*a*b的存储方式为{('a','a','b'):-1}
class Poly(Counter):
    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):
        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, varsMap):
        ans = Poly()
        for k, v in self.items():
            varNames = []
            cnt = v
            for varName in k:
                if varName not in varsMap:
                    varNames.append(varName)
                else:
                    cnt *= varsMap[varName]
            ans[tuple(varNames)] += cnt
        return ans

    # > 将多项式转为列表形式
    def toList(self):
        ans = []
        for k, v in sorted(self.items(), key = lambda item: (-len(item[0]), item[0], item[1])):
            if v:
                ans.append("*".join((str(v),) + k))
        return ans


class Solution:
    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
        # 思路：多项式类+递归+双栈
        varsMap = dict(zip(evalvars, evalints))
        # > make函数根据expr字符串将其转换为Poly对象，针对单个变量或单个整数的情况
        def make(expr):
            ans = Poly()
            if not expr[0].isdigit():
                ans.update({(expr,): 1})
            else:
                ans.update({(): int(expr)})
            return ans
        # > combine函数根据运算符号对Poly对象进行运算
        def combine(p1, p2, symbol):
            if symbol == "+":
                return p1 + p2
            elif symbol == "-":
                return p1 - p2
            elif symbol == "*":
                return p1 * p2
            raise
        # > 解析表达式的递归函数。返回expr字符串解析后的Poly多项式对象
        def parse(expr:str) -> Poly:
            n = len(expr)
            # 第一步，将当前层的表达式和符号分别用两个栈装着，其中表达式转换为Poly多项式对象
            i = 0
            buckets = []
            symbols = []
            while i < n:
                if expr[i] == "(":
                    # 1.1.遇到左括号，递归解析
                    j = i
                    a = 0
                    while j < n:
                        if expr[j] == "(":
                            a += 1
                        elif expr[j] == ")":
                            a -= 1
                        if a == 0:
                            break
                        j += 1
                    buckets.append(parse(expr[i + 1:j]))
                    i = j + 1
                elif expr[i].isalnum():
                    # 1.2.遇到字符或者数字，使用make函数将其解析为Poly对象
                    j = i
                    while j < n and expr[j] != " ":
                        j += 1
                    buckets.append(make(expr[i:j]))
                    i = j + 1
                elif expr[i] in "+-*":
                    # 1.3.遇到运算符，将其压入symbols栈中
                    symbols.append(expr[i])
                    i += 1
                else:
                    i += 1
            # 第二步，一次逆序遍历，将乘号进行运算；使用双栈进行
            buckets2 = []
            symbols2 = []
            while symbols:
                if symbols and symbols[-1] == "*":
                    p = combine(buckets.pop(), buckets.pop(), "*")
                    buckets.append(p)
                    symbols.pop()
                else:
                    buckets2.append(buckets.pop())
                    symbols2.append(symbols.pop())
            buckets2.append(buckets.pop())
            # 第三步，一次正向遍历，将加法和减法进行运算，并返回运算后的Poly对象
            while symbols2:
                p = combine(buckets2.pop(), buckets2.pop(), symbols2.pop())
                buckets2.append(p)
            return buckets2[0]
        # 第四步，调用parse解析expression，再将变量值代入运算，最后将得到的Poly对象转化为列表类型并返回
        p = parse(expression).evaluate(varsMap)
        return p.toList()

4.执行结果