0770. Basic Calculator IV

题目信息

题号:

0770

难度:

Hard

主题:

字符串、表达式求值、多项式规范化

原题:

LeetCode 0770

重点:

先用给定映射替换部分变量,再按括号、乘法、加减法规则化简;输出只保留非零项,并按次数降序及变量序列字典序排列

题目重述

给定一个合法算术表达式 expression,以及长度相同的数组 evalvars 和 evalints。对于每个下标 i,表达式中的变量 evalvars[i] 需要替换为整数 evalints[i];未被映射的变量继续作为自由变量保留。

表达式由非负整数、小写字母组成的变量、括号以及 +、-、* 构成。标记之间由单个空格分隔,运算优先级依次为括号、乘法、加减法。变量可以含多个字母,不带前置系数或一元符号。

请把替换并化简后的多项式返回为字符串数组。每个非零项中,自由变量按字典序排列并用 * 连接,重复变量需要重复列出;系数写在最前面,即使系数为 1 也不能省略。各项先按次数从高到低排列,次数相同时按忽略系数后的变量序列字典序排列;常数项次数为 0。系数为 0 的项不输出,因此零多项式返回空数组。

1 <= expression.length <= 250,映射变量数在 [0, 100] 范围内;变量名长度在 [1, 20] 范围内,映射值在 [-100, 100] 范围内。表达式保证合法,所有中间结果都在 32 位有符号整数范围内。

自建示例

替换部分变量并合并同类项:

输入:expression = "a * b + b * a + c", evalvars = ["b"], evalints = [2]
输出:["4*a","1*c"]
解释:把 b 替换为 2 后,两个乘积项分别成为 2*a,合并得到 4*a;c 未被替换而保留。两个一次项按变量名 a、c 的字典序排列。

相同项完全抵消:

输入:expression = "x * x - x * x + 7", evalvars = [], evalints = []
输出:["7"]
解释:两个 x*x 项系数相反,合并后为 0,不出现在结果中,只剩常数项 7。