目录

0770:基本计算器 IV(2863 分)

力扣第 770 题

题目

给定一个表达式如 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” 的表达式输出为 []

注意:你可以假设给定的表达式均有效。所有中间结果都在区间 [-231, 231 - 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

相似问题:

分析

本质上是多项式的计算。为了方便,考虑用 Counter() 存储变量和系数。

为了合并同类项,考虑用变量的有序元组来作为 key。常数项直接用空的元组作为 key。 比如 5 + a * b + bb * cc 表示为 {(): 5, (a, b): 1, (bb, cc): 1}。

具体实现时,括号内是 List(Counter) 的形式,先按顺序计算乘法,再按顺序计算加减,得到一个 Counter。 然后用栈模拟递归即可。

计算完毕后,所有单项式按 (元组长度, 元组本身) 排序,转为要求的字符串格式即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
    def mul(ct0, ct1):
        res = Counter()
        for k0, k1 in product(ct0, ct1):
            res[tuple(sorted(k0 + k1))] += ct0[k0] * ct1[k1]
        return res

    def cal(A):
        stack = []
        for item in A:
            if isinstance(item, dict) and stack and stack[-1] == '*':
                stack.pop()
                stack[-1] = mul(stack[-1], item)
            else:
                stack.append(item)
        res = Counter()
        for i in range(len(stack)):
            if isinstance(stack[i], dict):
                if i and stack[i - 1] == '-':
                    res.subtract(stack[i])
                else:
                    res.update(stack[i])
        return res

    stack, d = [[]], dict(zip(evalvars, evalints))
    for left, var, num, op, right in re.findall(r'(\()|([a-z]+)|(\d+)|([-+*])|(\))', expression):
        if left:
            stack.append([])
        elif var:
            stack[-1].append(Counter({(): d[var]} if var in d else {(var,): 1}))
        elif num:
            stack[-1].append(Counter({(): int(num)}))
        elif op:
            stack[-1].append(op)
        else:
            ct = cal(stack.pop())
            stack[-1].append(ct)
    res = sorted(cal(stack[0]).items(), key=lambda x: (-len(x[0]), x[0]))
    return ['*'.join((str(v),) + k) for k, v in res if v]

36 ms

*附加

本题不含正负号,所以和 0227 类似,可以用更通用的方法。 遍历到某个运算符时,将前面优先级更高的先运算了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
        def mul(ct0,ct1):
            ct2 = ct0.copy()
            ct0.clear()
            for a,b in product(ct1,ct2):
                ct0[tuple(sorted(a+b))] += ct1[a]*ct2[b]

        func = {'+': Counter.update, '-': Counter.subtract, '*': mul}
        pro =  dict(zip('*+-(', '1223'))
        d = dict(zip(evalvars,evalints))
        sk, ops = [], []
        for x,op in re.findall('([0-9a-z]+)|([-+*()])',expression+'+'):
            if x.isdigit():
                sk.append(Counter({():int(x)}))
            elif x.isalpha():
                sk.append(Counter({():d[x]} if x in d else {(x,):1}))
            elif op == '(':
                ops.append(op)
            elif op == ')':
                while ops[-1] != '(':
                    func[ops.pop()](sk[-2],sk.pop())
                ops.pop()
            else:
                while ops and pro[ops[-1]] <= pro[op]:
                    func[ops.pop()](sk[-2],sk.pop())
                ops.append(op)
        res = sorted(sk[0].items(), key=lambda x: (-len(x[0]), x[0]))
        return ['*'.join((str(v),)+k) for k,v in res if v]

52 ms