0770. Basic Calculator IV¶
题目信息¶
- 题号:
0770
- 难度:
Hard
- 主题:
字符串、表达式求值、多项式规范化
- 原题:
- 重点:
先用给定映射替换部分变量,再按括号、乘法、加减法规则化简;输出只保留非零项,并按次数降序及变量序列字典序排列
题目重述¶
给定一个合法算术表达式 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。