LeetCode 770. 基本计算器 IV
题目描述
题意分析
表达式包含整数、变量、加减乘和括号。给定赋值的变量要替换为整数，未赋值的变量继续保留为符号；按通常的运算优先级展开并合并同类项，输出系数不为零的各项。
每项内部的变量名按字典序排列，重复变量不能删除；各项先按次数降序排列，次数相同再按变量序列的字典序排列，比较时不看系数。即使系数为
1也要输出，常数项只输出数值，整个结果为零时返回空列表。
解法：多项式 + 递归解析
核心思路
[!blue]
普通计算器在递归中返回一个数，本题则让每个子表达式返回一个多项式。用
terms哈希表表示它：键是排序后用*连接的变量名序列，值是这一项的系数。常数没有变量，用空字符串作键；单个未赋值变量的系数为1；零多项式用空表表示。规范键只消除乘法顺序的差异，不消除变量的重复次数。两个单项式的变量及其出现次数相同，排序后的键就相同，应该合并系数；变量不同或次数不同，键就不同，不能合并。变量名可能含多个字母，必须先按完整名字拆分和排序，不能按字符处理。
多项式加减法先复制左边各项，再将右边同键系数逐个加上或减去。乘法按照分配律枚举两边的每一对项：系数相乘，变量序列合并后排序，得到乘积项的规范键，再把系数累加到结果表。多个项对可能产生同一个键，因此这里必须累加，不能覆盖。每次运算后删除系数为零的项，使后续运算只处理仍有贡献的项。
解析按优先级分成三层。
parseExpr()处理加减，每个操作数先交给parseTerm()；parseTerm()处理连续乘法，每个因子再交给parseFactor()。因此乘法会先合并成完整多项式，再参与外层加减。各层从左到右不断更新res，也就正确保留了连续减法的结合顺序。
parseFactor()负责整数、变量和括号。整数返回常数多项式；变量在赋值表中存在时返回对应常数，否则保留符号项。判断的是“是否存在绑定”，不能判断绑定值是否为零，因为代入零同样有意义，且会直接得到空多项式。遇到左括号时，
parseFactor()消费它并递归调用parseExpr()；内层表达式看到右括号只停止，不消费它，再由发起递归的因子层消费这个右括号。共享游标idx因而始终指向尚未处理的位置，嵌套表达式不会多吃或漏吃括号。基本因子得到正确多项式后，加减法按同类项规则、乘法按分配律保持等值，所以逐层返回的结果都与对应子表达式等价。最终把所有非零项按次数和规范键排序：次数是变量出现的总个数，常数次数为零。非空键输出为
系数*变量串，空键直接输出系数，即满足题目的格式要求。
解题步骤
- 建立变量赋值表。
- 解析括号与优先级，变量有赋值则直接变常数。
- 执行多项式加减乘，同类项使用相同规范键。
- 丢弃零项，按次数与字典序输出。
题目保证表达式合法，数字因子是非负整数，变量名前不会出现一元负号或省略乘号的系数。负系数可以由减法或变量代入产生，仍按普通系数处理。若所有项都抵消，项表为空，输出自然为空列表；题目也保证运算的中间结果在 32 位整数范围内。
代码实现
class Solution {
public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
Map<String, Integer> eval = new HashMap<>();
for (int i = 0; i < evalvars.length; i++) {
eval.put(evalvars[i], evalints[i]);
}
Parser parser = new Parser(expression, eval);
Poly poly = parser.parseExpr();
return poly.toList();
}
private static class Parser {
private final String s;
private final Map<String, Integer> eval;
private int idx;
Parser(String s, Map<String, Integer> eval) {
this.s = s;
this.eval = eval;
this.idx = 0;
}
// 加减层调用乘法层，按嵌套层级表达优先级
Poly parseExpr() {
Poly res = parseTerm();
while (true) {
skipSpaces();
if (idx >= s.length() || s.charAt(idx) == ')') {
break;
}
char op = s.charAt(idx);
if (op != '+' && op != '-') {
break;
}
idx++;
Poly right = parseTerm();
if (op == '+') {
res = res.add(right);
} else {
res = res.sub(right);
}
}
return res;
}
Poly parseTerm() {
Poly res = parseFactor();
while (true) {
skipSpaces();
if (idx >= s.length() || s.charAt(idx) != '*') {
break;
}
idx++;
Poly right = parseFactor();
res = res.mul(right);
}
return res;
}
Poly parseFactor() {
skipSpaces();
char ch = s.charAt(idx);
// 基本因子负责消费成对括号，内部表达式遇右括号只返回
if (ch == '(') {
idx++;
Poly res = parseExpr();
skipSpaces();
idx++;
return res;
}
if (Character.isLetter(ch)) {
String var = parseToken();
// 已绑定变量立即代入，包括零；其余变量保留符号项。
if (eval.containsKey(var)) {
return new Poly(eval.get(var));
}
return Poly.ofVar(var);
}
int sign = 1;
if (ch == '-') {
sign = -1;
idx++;
}
int num = 0;
while (idx < s.length() && Character.isDigit(s.charAt(idx))) {
num = num * 10 + (s.charAt(idx) - '0');
idx++;
}
return new Poly(sign * num);
}
String parseToken() {
int start = idx;
while (idx < s.length()) {
char ch = s.charAt(idx);
if (ch == ' ' || ch == ')' || ch == '+' || ch == '-' || ch == '*') {
break;
}
idx++;
}
return s.substring(start, idx);
}
void skipSpaces() {
while (idx < s.length() && s.charAt(idx) == ' ') {
idx++;
}
}
}
private static class Poly {
private final Map<String, Integer> terms = new HashMap<>();
Poly() {}
Poly(int constant) {
if (constant != 0) {
terms.put("", constant);
}
}
static Poly ofVar(String var) {
Poly p = new Poly();
p.terms.put(var, 1);
return p;
}
Poly add(Poly other) {
Poly res = new Poly();
res.terms.putAll(this.terms);
for (Map.Entry<String, Integer> e : other.terms.entrySet()) {
res.terms.put(e.getKey(), res.terms.getOrDefault(e.getKey(), 0) + e.getValue());
}
res.cleanup();
return res;
}
Poly sub(Poly other) {
Poly res = new Poly();
res.terms.putAll(this.terms);
for (Map.Entry<String, Integer> e : other.terms.entrySet()) {
res.terms.put(e.getKey(), res.terms.getOrDefault(e.getKey(), 0) - e.getValue());
}
res.cleanup();
return res;
}
Poly mul(Poly other) {
Poly res = new Poly();
for (Map.Entry<String, Integer> a : this.terms.entrySet()) {
for (Map.Entry<String, Integer> b : other.terms.entrySet()) {
// 乘法按变量多重集合规范化，同类项还要累积系数
String key = mergeKey(a.getKey(), b.getKey());
int val = a.getValue() * b.getValue();
res.terms.put(key, res.terms.getOrDefault(key, 0) + val);
}
}
res.cleanup();
return res;
}
List<String> toList() {
List<String> keys = new ArrayList<>(terms.keySet());
keys.removeIf(k -> terms.get(k) == 0);
Collections.sort(
keys,
(a, b) -> {
int da = degree(a);
int db = degree(b);
if (da != db) {
return db - da;
}
return a.compareTo(b);
});
List<String> res = new ArrayList<>();
for (String key : keys) {
int coef = terms.get(key);
if (coef == 0) {
continue;
}
if (key.isEmpty()) {
res.add(String.valueOf(coef));
} else {
res.add(coef + "*" + key);
}
}
return res;
}
private void cleanup() {
terms.entrySet().removeIf(e -> e.getValue() == 0);
}
private int degree(String key) {
if (key.isEmpty()) {
return 0;
}
// 次数按变量个数计算，重复变量不能去重
return key.split("\\*").length;
}
private String mergeKey(String a, String b) {
if (a.isEmpty()) {
return b;
}
if (b.isEmpty()) {
return a;
}
String[] pa = a.split("\\*");
String[] pb = b.split("\\*");
List<String> list = new ArrayList<>();
Collections.addAll(list, pa);
Collections.addAll(list, pb);
Collections.sort(list);
return String.join("*", list);
}
}
}
import (
"sort"
"strconv"
"strings"
)
type Poly struct {
terms map[string]int
}
func newPoly() Poly {
return Poly{terms: make(map[string]int)}
}
func constPoly(val int) Poly {
p := newPoly()
if val != 0 {
p.terms[""] = val
}
return p
}
func varPoly(name string) Poly {
p := newPoly()
p.terms[name] = 1
return p
}
func (p Poly) add(o Poly) Poly {
res := newPoly()
for k, v := range p.terms {
res.terms[k] = v
}
for k, v := range o.terms {
res.terms[k] += v
}
res.cleanup()
return res
}
func (p Poly) sub(o Poly) Poly {
res := newPoly()
for k, v := range p.terms {
res.terms[k] = v
}
for k, v := range o.terms {
res.terms[k] -= v
}
res.cleanup()
return res
}
func (p Poly) mul(o Poly) Poly {
res := newPoly()
for ak, av := range p.terms {
for bk, bv := range o.terms {
// 乘法按变量多重集合规范化，同类项还要累积系数
key := mergeKey(ak, bk)
res.terms[key] += av * bv
}
}
res.cleanup()
return res
}
func (p Poly) toList() []string {
keys := make([]string, 0, len(p.terms))
for k, v := range p.terms {
if v != 0 {
keys = append(keys, k)
}
}
sort.Slice(keys, func(i, j int) bool {
di := degree(keys[i])
dj := degree(keys[j])
if di != dj {
return di > dj
}
return keys[i] < keys[j]
})
res := make([]string, 0, len(keys))
for _, key := range keys {
coef := p.terms[key]
if key == "" {
res = append(res, strconv.Itoa(coef))
} else {
res = append(res, strconv.Itoa(coef)+"*"+key)
}
}
return res
}
func (p Poly) cleanup() {
for k, v := range p.terms {
if v == 0 {
delete(p.terms, k)
}
}
}
func degree(key string) int {
if key == "" {
return 0
}
// 次数按变量个数计算，重复变量不能去重
return len(strings.Split(key, "*"))
}
func mergeKey(a string, b string) string {
if a == "" {
return b
}
if b == "" {
return a
}
parts := append(strings.Split(a, "*"), strings.Split(b, "*")...)
sort.Strings(parts)
return strings.Join(parts, "*")
}
type Parser struct {
s string
idx int
eval map[string]int
}
func basicCalculatorIV(expression string, evalvars []string, evalints []int) []string {
eval := make(map[string]int)
for i := 0; i < len(evalvars); i++ {
eval[evalvars[i]] = evalints[i]
}
p := Parser{s: expression, idx: 0, eval: eval}
poly := p.parseExpr()
return poly.toList()
}
// 加减层调用乘法层，按嵌套层级表达优先级
func (p *Parser) parseExpr() Poly {
res := p.parseTerm()
for {
p.skipSpaces()
if p.idx >= len(p.s) || p.s[p.idx] == ')' {
break
}
op := p.s[p.idx]
if op != '+' && op != '-' {
break
}
p.idx++
right := p.parseTerm()
if op == '+' {
res = res.add(right)
} else {
res = res.sub(right)
}
}
return res
}
func (p *Parser) parseTerm() Poly {
res := p.parseFactor()
for {
p.skipSpaces()
if p.idx >= len(p.s) || p.s[p.idx] != '*' {
break
}
p.idx++
right := p.parseFactor()
res = res.mul(right)
}
return res
}
func (p *Parser) parseFactor() Poly {
p.skipSpaces()
ch := p.s[p.idx]
// 基本因子负责消费成对括号，内部表达式遇右括号只返回
if ch == '(' {
p.idx++
res := p.parseExpr()
p.skipSpaces()
p.idx++
return res
}
if ch >= 'a' && ch <= 'z' {
name := p.parseToken()
// 已绑定变量立即代入，包括零；其余变量保留符号项。
if val, ok := p.eval[name]; ok {
return constPoly(val)
}
return varPoly(name)
}
sign := 1
if ch == '-' {
sign = -1
p.idx++
}
num := 0
for p.idx < len(p.s) {
c := p.s[p.idx]
if c < '0' || c > '9' {
break
}
num = num*10 + int(c-'0')
p.idx++
}
return constPoly(sign * num)
}
func (p *Parser) parseToken() string {
start := p.idx
for p.idx < len(p.s) {
ch := p.s[p.idx]
if ch == ' ' || ch == ')' || ch == '+' || ch == '-' || ch == '*' {
break
}
p.idx++
}
return p.s[start:p.idx]
}
func (p *Parser) skipSpaces() {
for p.idx < len(p.s) && p.s[p.idx] == ' ' {
p.idx++
}
}
复杂度分析
- 时间复杂度：设 L 为表达式长度、B 为代入变量数、T 为最大中间项数、D 为最大单项次数：解析与建表 $O(L+B)$；一次乘法至多 $O(T^2(D+1)\log(D+2))$，至多 $O(L)$ 次多项式运算；输出排序另需 $O(T\log(T+1)(D+1))$。这里按变量名长度有界估算。
- 空间复杂度：$O(L+B+(h+1)T(D+1))$，h 为解析深度。父层尚未合并的多项式也会保留，不能只计算当前的一张项表。
T要按运算过程中实际出现的项数计算，不能只看最终答案有多少项：展开可能先产生许多项，再在后续加减中大量抵消。每次乘法枚举项对、排序变量串的成本，也不能计入单纯的线性字符扫描而忽略。
关键点总结
[!green]
- 规范化的是变量多重集合，不能将 a*a 去重成 a。
- 基本因子负责成对消费括号，外层看到右括号只停止。
易错点总结
[!yellow]
- 变量串不排序，会把 ab 与 ba 当作不同项。
- 乘法同类项直接覆盖，会丢掉其他项对的贡献。
- 只按字典序输出，会把一次项 a 排在二次项 z*z 前面。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 772. 基本计算器 III | 困难 | 表达式解析与优先级相同，本题还保留未替换变量并合并多项式同类项。 |
| 224. 基本计算器 | 困难 | 计算器系列。I 是只有加减和括号的数值版本，可先复用其递归解析结构，再扩展多项式运算。 |
| 227. 基本计算器 II | 中等 | 计算器系列。II 聚焦乘除优先级与数值求值；IV 沿用优先级解析，并扩展变量及多项式表示。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！