题目描述：

LeetCode 770. Basic Calculator IV

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"]

• An expression alternates chunks and symbols, with a space separating each chunk and symbol.
• A chunk is either an expression in parentheses, a variable, or a non-negative integer.
• A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like "2x" or "-x".

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:

• For each term of free variables with non-zero coefficient, we write the free variables within a term in sorted order lexicographically. For example, we would never write a term like "b*a*c", only "a*b*c".
• Terms have degree equal to the number of free variables being multiplied, counting multiplicity. (For example, "a*a*b*c" has degree 4.) We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
• The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.)  A leading coefficient of 1 is still printed.
• An example of a well formatted answer is ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"] 
• Terms (including constant terms) with coefficient 0 are not included.  For example, an expression of "0" has an output of [].

Examples:

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: ["1*e*e","-64"]

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

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

Input: expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))",
evalvars = [], evalints = []
Output: ["-1*a*a*b*b","2*a*a*b*c","-1*a*a*c*c","1*a*b*b*b","-1*a*b*b*c","-1*a*b*c*c","1*a*c*c*c","-1*b*b*b*c","2*b*b*c*c","-1*b*c*c*c","2*a*a*b","-2*a*a*c","-2*a*b*b","2*a*c*c","1*b*b*b","-1*b*b*c","1*b*c*c","-1*c*c*c","-1*a*a","1*a*b","1*a*c","-1*b*c"]

Note:

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

题目大意：

模拟实现多项式加减乘法

解题思路：

栈（Stack）

Python代码：

class Solution(object):
    def calc(self, op, left, right):
        if op == '+':
            left.update(right)
            return left
        if op == '-':
            left.subtract(right)
            return left
        ans = collections.Counter()
        for lk, lv in left.items():
            for rk, rv in right.items():
                nk = tuple(sorted(lk + rk)) if lk and rk else lk or rk
                ans[nk] += lv * rv
        return ans

    def basicCalculatorIV(self, expression, evalvars, evalints):
        """
        :type expression: str
        :type evalvars: List[str]
        :type evalints: List[int]
        :rtype: List[str]
        """
        evaldict = {v : i for v, i, in zip(evalvars, evalints)}
        s = re.sub(r'[\d\w]+', ' \g<0> ', expression)
        s = re.sub(r'\(', ' ( ', s)
        s = re.sub(r'\)', ' ) ', s)
        expression = [str(evaldict.get(t, t)) for t in s.split()]
        idx = 0
        part = collections.Counter()
        operands, operators = [part], []
        while idx < len(expression):
            e = expression[idx]
            if e == '(':
                operators.append(e)
            elif e == ')':
                while operators[-1] != '(':
                    right, left = operands.pop(), operands.pop()
                    operands.append(self.calc(operators.pop(), left, right))
                operators.pop()
            elif e in '+-':
                while operators and operators[-1] in '+-*':
                    right, left = operands.pop(), operands.pop()
                    operands.append(self.calc(operators.pop(), left, right))
                operators.append(e)
            elif e == '*':
                operators.append(e)
            else:
                part = collections.Counter()
                if e.replace('-', '').isdigit(): part[''] += int(e)
                else: part[tuple([e])] += 1
                operands.append(part)
            idx += 1
        while operators:
            right, left = operands.pop(), operands.pop()
            operands.append(self.calc(operators.pop(), left, right))
        ans = sorted(operands[-1].items(), key = lambda x: (-len(x[0]), x[0]))
        return [str(v) + (k and '*' + '*'.join(k) or '') for k, v in ans if v]

 

本文链接：http://bookshadow.com/weblog/2018/01/24/leetcode-basic-calculator-iv/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码