foolish fly fox's blog

--Stay hungry, stay foolish.
--Forever young, forever weep.



770. Basic Calculator IV

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

Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {"e": 1} (given in terms of evalvars = ["e"] and evalints = [1]), return a list of tokens representing the simplified expression, such as ["-1*a","14"]

Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction. For example, expression = "1 + 2 * 3" has an answer of ["7"].

The format of the output is as follows:

Example:

Input: expression= "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
Output: ["-1*a","14"]

Input: expression = "e - 8 + temperature - pressure",
evalvars = ["e", "temperature"], evalints = [1, 12]
Output: ["-1*pressure","5"]

Input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
Output: ["1ee","-64"]

Input: expression = "7 - 7", evalvars = [], evalints = []
Output: []

Input: expression = "a * b * c + b * a * c * 4", evalvars = [], evalints = []
Output: ["5ab*c"]

Input: expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))", evalvars = [], evalints = []
Output: ["-1aabb","2aabc","-1aacc","1abbb","-1abbc","-1abcc","1accc","-1bbbc","2bbcc","-1bccc","2aab","-2aac","-2abb","2acc","1bbb","-1bbc","1bcc","-1ccc","-1aa","1ab","1ac","-1bc"]

Note:

  1. expression will have length in range [1, 250].
  2. evalvars, evalints will have equal lengths in range [0, 100].

Solution

def basicCalculatorIV(self, expression, evalvars, evalints):
    class C(collections.Counter):
        def __add__(self, other):
            self.update(other)
            return self
        def __sub__(self, other):
            self.subtract(other)
            return self
        def __mul__(self, other):
            product = C()
            for x in self:
                for y in other:
                    xy = tuple(sorted(x + y))
                    product[xy] += self[x] * other[y]
            return product
    vals = dict(zip(evalvars, evalints))
    def f(s):
        s = str(vals.get(s, s))
        return C({(s,): 1}) if s.isalpha() else C({(): int(s)})
    c = eval(re.sub('(\w+)', r'f("\1")', expression))
    return ['*'.join((str(c[x]),) + x)
            for x in sorted(c, key=lambda x: (-len(x), x))
            if c[x]]

Analysis

将两个数组合并为一个dict类型

keys = list("abc")
values = [1,2,3]
print(list(zip(keys,values)))
print(dict(zip(keys,values)))
▶︎
all
running...
[('a', 1), ('b', 2), ('c', 3)]
{'a': 1, 'b': 2, 'c': 3}

re 模块

该模块用于提供正则表达式匹配的功能。