基本计算器 IV

770. 基本计算器 IV

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

表达式交替使用块和符号，每个块和符号之间有一个空格。
块要么是括号中的表达式，要么是变量，要么是非负整数。
变量是一个由小写字母组成的字符串（不包括数字）。请注意，变量可以是多个字母，并注意变量从不具有像 "2x" 或 "-x" 这样的前导系数或一元运算符。

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

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

输出格式如下：

对于系数非零的每个自变量项，我们按字典排序的顺序将自变量写在一个项中。
- 例如，我们永远不会写像 “b*a*c” 这样的项，只写 “a*b*c”。
项的次数等于被乘的自变量的数目，并计算重复项。我们先写出答案的最大次数项，用字典顺序打破关系，此时忽略词的前导系数。
- 例如，"a*a*b*c" 的次数为 4。
项的前导系数直接放在左边，用星号将它与变量分隔开(如果存在的话)。前导系数 1 仍然要打印出来。
格式良好的一个示例答案是 ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"] 。
系数为 0 的项（包括常数项）不包括在内。
- 例如，“0” 的表达式输出为 [] 。

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

示例 1：

输入：expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
输出：["-1*a","14"]

示例 2：

输入：expression = "e - 8 + temperature - pressure",
evalvars = ["e", "temperature"], evalints = [1, 12]
输出：["-1*pressure","5"]

示例 3：

输入：expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
输出：["1*e*e","-64"]

提示：

1 <= expression.length <= 250
expression 由小写英文字母，数字 '+', '-', '*', '(', ')', ' ' 组成
expression 不包含任何前空格或后空格
expression 中的所有符号都用一个空格隔开
0 <= evalvars.length <= 100
1 <= evalvars[i].length <= 20
evalvars[i] 由小写英文字母组成
evalints.length == evalvars.length
-100 <= evalints[i] <= 100

相似题目

Lisp 语法解析

基本计算器 III

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) { } };

python3 解法, 执行用时: 52 ms, 内存消耗: 16.4 MB, 提交时间: 2023-05-24 17:38:32

class Solution:
    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
        # 通用双栈+全局分词+元组计数字典+处理首尾括号+排除计数0
        # 计数字典的key是元组, 方便排序处理, 其中空元组代表常量
        maps = {}
        for v, i in zip(evalvars, evalints):
            maps[v] = i
        # 全局按照空格分词
        tokens = expression.split()
        # 操作符的优先级
        pri = {
            "(": 0,
            "+": 1,
            "-": 1,
            "*": 2,
        }
        # 数字栈和符号栈
        numStack, opStack = [], []

        def calTwo():
            # 计算栈顶
            if len(numStack) < 2 or len(opStack) < 1:
                return
            op = opStack.pop()
            b = numStack.pop()
            a = numStack.pop()
            c = collections.defaultdict(int)
            if op == "*":
                # 两重循环求乘积
                for k1 in a:
                    for k2 in b:
                        # 新的key要按照字典序排序
                        k = tuple(sorted(k1 + k2))
                        # 新的计数是原计数相乘
                        c[k] += a[k1] * b[k2]
            else:
                # 求和或求差
                c = a.copy()
                for k in b:
                    if op == "+":
                        c[k] += b[k]
                    else:
                        c[k] -= b[k]
            numStack.append(c)

        def convert(token):
            # 将当前分词转换成元组计数字典
            d = collections.defaultdict(int)
            # 注意key都是元组, 常量是空元组, 变量是包含自身的元组
            if token in maps:
                d[()] = maps[token]
            elif token.isnumeric():
                d[()] = int(token)
            else:
                d[(token,)] = 1
            return d

        for t in tokens:
            if t in pri:
                # 当前token是操作符
                op = t
                while opStack and pri[opStack[-1]] >= pri[op]:
                    # 栈顶优先级更高, 先计算它
                    calTwo()
                opStack.append(op)
            else:
                # 先处理首尾括号, 注意括号都可能有多个, 且可以同时存在于一个token中
                # 例如((a + b) * (c + d)) + (e)
                # 左右非括号边界
                l, r = 0, len(t) - 1
                # 右括号数目
                rcnt = 0
                while l < r and t[l] == "(":
                    # 将左括号压入栈中
                    opStack.append("(")
                    l += 1
                while l < r and t[r] == ")":
                    rcnt += 1
                    r -= 1
                # 处理完括号后, 剩余部分转换后压入栈中
                numStack.append(convert(t[l : r + 1]))
                while rcnt > 0:
                    # 循环处理累积的右括号, 不断弹出并计算栈顶, 直到栈顶是最近的左括号
                    while opStack and opStack[-1] != "(":
                        calTwo()
                    # 注意当前栈顶是左括号, 需要额外将其弹出
                    opStack.pop()
                    rcnt -= 1

        while opStack:
            # 如果仍有剩余的操作数, 计算它们
            calTwo()
        # 栈中唯一元素即为最终的元组计数字典
        d = numStack[0]
        res = []
        # 将key按照长度递减, 字母递增的顺序排列
        skeys = sorted(d.keys(), key=lambda t: (-len(t), t))
        for k in skeys:
            cnt = d[k]
            if cnt != 0:
                # 注意排除计数为0的项!!!
                key = "*".join(k)
                # 如果是常数, 则key是空字符串, 不带*
                item = f"{cnt}*{key}" if key != "" else str(cnt)
                res.append(item)
        return res

上一题

下一题

详情