企业官网建设流程全解析

LeetCode 770 在我的刷题笔记里代号是“豆包题”。起这个名字那天，我刚打开题目，手边正好有一袋豆包，心想这种“表达式展开”题撑死半小时就能搞定，结果豆包热了三回，我才把第一个版本跑通。事后复盘，它卡人的地方根本不在算法，而在于一道题同时塞进了表达式解析、变量替换、多项式乘法展开、同类项合并，以及一套非常拗口的排序规则。任何一环想得不细，输出就跟你预期差一个量级。

这篇内容不是单纯贴一份能过的代码，而是把我从“不知道从哪下手”到“能对着编译错误和答案差异一眼定位问题”的完整过程拆开讲。适合已经刷过基础计算器系列、想挑战 Hard 的选手，也适合正在准备面试、想练表达式与数据结构设计的人。

1. 先看清楚题目到底在问什么：一条表达式、两张替换表、一套输出规则

1.1 三种输入和它们各自的“坑”

这道题的方法签名是public List<String> basicCalculatorIV(String expression, List<String> evalvars, List<Integer> evalints)，输入比基础计算器系列多了一个变量赋值机制。

expression是一条合法的表达式，包含数字、小写字母开头的变量、+、-、*、括号和空格。数字不带前导零；变量可以由小写字母开头，后面继续跟小写字母和数字，比如a1b是一个完整的变量名，不能拆成a、1、b处理。

evalvars和evalints是配套的两张表：evalvars[i]这个名字的变量，在整个表达式里要用evalints[i]这个整数替换。这里第一个容易踩的坑是：替换发生在化简之前，不是最后输出前。如果表达式里有x * x，而x = 2，你必须在看到x的瞬间就把它变成常量2。要是等到合并完同类项、得到x*x这一项后才想起来替换，那已经晚了，因为x*x是作为“两个变量的乘积项”存在的，没法再回溯到数值。

我习惯把这两种输入看成两条处理线索：一条是“表达式本身的结构”，另一条是“变量名到数值的映射”。在代码里映射用一个Map<String, Long>存起来，解析变量 token 时先查表，查得到就返回常量多项式，查不到才当成自由变量。

1.2 输出排序：degree 优先、变量字典序次之、常数垫底

输出格式是本题最容易被扣分的地方。最终合并完同类项后，每个非零项要转成一个字符串，按“标准序”排列返回。

标准序的规则可以拆成三层：

1. 先按变量个数从多到少排，也就是多项式的 degree（次数）降序。注意变量是可以重复的，a*a*b算 3 个变量，degree 是 3。
2. 变量个数相同时，按变量的字典序升序排。比如 degree 都是 2 的两项，a*b排在a*c前面。
3. degree 是 0 的项就是纯常数，放在最后。如果整个化简结果为 0，也就是没有任何非零项，返回空列表[]，不能输出一个"0"。

举个例子，表达式"e + 8 - a + 5"，没有变量赋值。合并常数8 + 5 = 13，剩下的自由变量是-a + e。两个单项的 degree 都是 1，按变量字典序a在e前面，所以结果是["-1*a", "1*e", "13"]。

还有两个输出格式细节：

• 只要这一项不是纯常数，系数就必须显式写出来，哪怕系数是1或-1，也要写"1*e"、"-1*a"。
• 纯常数项直接输出数字字符串，比如"13"。常数项为 0 时直接丢弃，不参与输出。

2. 多项式对象设计：为什么一张 Map 能把加减乘和同类项一起搞定

2.1 选 key 的细节：排序后的变量连乘串

拿到题目我第一个想法是：把整个表达式当成“多项式”来算。一个多项式本质上就是一堆“变量组合 + 系数”的项，比如-2*a*b + 3*c + 5。所以我直接设计一个Poly类，内部用一个Map<String, Long>存所有项：key 是变量组合，value 是系数。

这个 key 怎么定，是整个设计里最影响代码量的一步。我采用的做法是：把一个项里出现的所有变量名按字典序排序，然后用"*"连接成字符串，作为 key。

• a*b的 key 就是"a*b"。
• b*a排序后也是"a*b"，这样乘法里a*b和b*a自然合并成一项。
• 变量可以重复出现，比如a*a*b的 key 是"a*a*b"，不化简成指数形式，输出时也是展开写。

为什么用字符串而不是List<String>当 key？字符串可以直接放进HashMap，合并两个项的变量组合时，把两份变量拼在一起再排序、再join，逻辑非常简单。输出时也能直接拼在系数后面。唯一要小心的就是变量名里不会出现*，所以用"*"做分隔符绝对安全。

纯常数项怎么办？我让它的 key 是空字符串""。这样所有运算都可以统一：加法就是把系数相加，乘法就是把两组变量组合合并。

2.2 add / sub / mul 三件套的代码实现

Poly类核心就三个静态方法：add、sub、mul。每次运算返回一个新对象，不在原对象上原地修改，这样调试时不容易互相污染。

class Poly { // key: 排好序的变量连乘串，如 "a*b"；value: 系数 Map<String, Long> terms = new HashMap<>(); Poly() {} Poly(long constVal) { if (constVal != 0) { terms.put("", constVal); } } // 添加一个单项，如果合并后系数为 0，就把这一项删掉 void addTerm(String key, long coeff) { terms.merge(key, coeff, Long::sum); if (terms.get(key) == 0) { terms.remove(key); } } static Poly add(Poly a, Poly b) { Poly res = new Poly(); res.terms.putAll(a.terms); for (Map.Entry<String, Long> e : b.terms.entrySet()) { res.addTerm(e.getKey(), e.getValue()); } return res; } static Poly sub(Poly a, Poly b) { Poly res = new Poly(); res.terms.putAll(a.terms); for (Map.Entry<String, Long> e : b.terms.entrySet()) { res.addTerm(e.getKey(), -e.getValue()); } return res; } static Poly mul(Poly a, Poly b) { Poly res = new Poly(); for (Map.Entry<String, Long> e1 : a.terms.entrySet()) { for (Map.Entry<String, Long> e2 : b.terms.entrySet()) { String key = combineKey(e1.getKey(), e2.getKey()); long coeff = e1.getValue() * e2.getValue(); res.addTerm(key, coeff); } } return res; } // 把两个变量组合串合并成一个排好序的新组合串 static String combineKey(String k1, String k2) { if (k1.isEmpty()) return k2; if (k2.isEmpty()) return k1; String[] v1 = k1.split("\\*"); String[] v2 = k2.split("\\*"); String[] all = new String[v1.length + v2.length]; System.arraycopy(v1, 0, all, 0, v1.length); System.arraycopy(v2, 0, all, v1.length, v2.length); Arrays.sort(all); return String.join("*", all); } }

sub的实现有个小细节：我没有单独写“取负”，而是在遍历第二个多项式时，直接把系数取相反数再addTerm。这样减少一次中间对象的创建，逻辑也更统一。

乘法是 O(n*m) 的双层循环，n 和 m 分别代表两个多项式的项数。这里没法优化成更快的多项式乘法，因为题目规模本身不大，重点是保证正确性。最坏情况下乘法的展开确实可能让项数指数膨胀，但这是题目本身的属性，不是实现逼出来的。

2.3 evalvars 替换必须做在 token 层：一个反面例子

这是我第一版代码最惨痛的教训。我最初的设计是：先解析出完整表达式，把所有变量都当作自由变量，最后再统一替换evalvars。结果遇到x = 2、表达式"x * x"时，化简得到的是 key 为"x*x"、系数为 1 的单项。这时候我想把x替换成2，但"x*x"里已经有两个x联合在一起了，我根本不知道该怎么回代。

正确的做法是：在parseFactor里读到变量 token 时，立刻查evalMap。查到了就返回一个常数多项式Poly(constant)，查不到才返回单项式Poly（key 就是变量名）。这样"x * x"在x = 2时，两个因子会分别变成常数2，乘法结果直接是常数4，整个过程根本不会出现"x*x"这个 key。

这个决策要尽早做，因为 evalvars 的初衷就是把某些变量“降维”成常量，而降维发生在解析阶段最彻底。

3. 递归下降解析器：让每个字符都找到自己的归处

3.1 三个函数对应三个优先级

表达式只有三种运算符：+ -优先级最低，*优先级居中，括号优先级最高。所以解析器只需要三层递归，不需要搞运算符优先级的通用算法。

• parseExpr()：解析加减法，内部调用parseTerm()。
• parseTerm()：解析乘法，内部调用parseFactor()。
• parseFactor()：解析基础因子，处理括号、数字、变量。

这个结构我不依赖 Token 列表，直接在一个字符串上用索引pos扫。每次读到+或-，就继续往右读一个 term，再把两个多项式相加或相减；读到*就继续往右读一个 factor，做乘法。

Poly parseExpr() { Poly cur = parseTerm(); while (pos < s.length() && (s.charAt(pos) == '+' || s.charAt(pos) == '-')) { char op = s.charAt(pos); pos++; Poly rhs = parseTerm(); if (op == '+') { cur = Poly.add(cur, rhs); } else { cur = Poly.sub(cur, rhs); } } return cur; } Poly parseTerm() { Poly cur = parseFactor(); while (pos < s.length() && s.charAt(pos) == '*') { pos++; Poly rhs = parseFactor(); cur = Poly.mul(cur, rhs); } return cur; }

这个写法和“把中缀表达式转后缀再求值”相比，好处是括号天然递归处理，不需要运算符栈。坏处是每一层都要小心pos是否越界。不过因为题目保证表达式合法，解析到末尾时一定已经消费完整条字符串。

3.2 parseFactor 里的三个分支与变量命名的坑

parseFactor需要处理三种情况：括号、数字、变量。我习惯在开头先处理括号，因为括号后面跟的一定是一个完整的表达式。

Poly parseFactor() { if (s.charAt(pos) == '(') { pos++; Poly inner = parseExpr(); pos++; // 跳过 ')' return inner; } if (Character.isDigit(s.charAt(pos))) { long val = 0; while (pos < s.length() && Character.isDigit(s.charAt(pos))) { val = val * 10 + (s.charAt(pos) - '0'); pos++; } return new Poly(val); } // 变量：首字符是字母，后续可以是字母或数字 int start = pos; while (pos < s.length() && (Character.isLetter(s.charAt(pos)) || Character.isDigit(s.charAt(pos)))) { pos++; } String var = s.substring(start, pos); if (evalMap.containsKey(var)) { return new Poly(evalMap.get(var)); } Poly p = new Poly(); p.addTerm(var, 1); return p; }

变量读取的 while 条件里，我用的是Character.isLetter和Character.isDigit，而不是只判断a到z。题目说明变量由小写字母和数字组成，但在代码层面统一用isLetter更稳，万一测试里出现大写字母也不会崩。当然题目明确说小写，这只是我个人的防御式习惯。

还有一个细节：数字解析用的是long而不是int。虽然题目给的数值范围不大，但多项式乘法展开后系数可能成倍增长，用long至少能多扛一阵。

3.3 主流程整合：一行去掉空格，剩下交给递归

主方法非常简单，把空格清掉，建好 evalMap，然后让parseExpr去处理整条表达式。

public List<String> basicCalculatorIV(String expression, List<String> evalvars, List<Integer> evalints) { for (int i = 0; i < evalvars.size(); i++) { evalMap.put(evalvars.get(i), (long) evalints.get(i)); } s = expression.replace(" ", ""); poly = parseExpr(); return formatResult(poly); }

这里注意：expression.replace(" ", "")会把所有空格删掉，而题目保证空格只会出现在 token 之间，不会出现在变量名内部，所以删除空格是安全的。如果题目允许空格出现在字符串字面量里，那这套写法就不成立，但这里显然不会。

4. 从散乱 Map 到有序答案：排序 comparator 里的两个优先级的真相

4.1 comparator 怎么写得短且不出错

Poly里的terms是一张 Map，遍历时没有顺序概念。所以我需要把每一项取出来，按照题目的标准序排序。

排序我不打算用字符串直接比。因为字符串"a*b"和"a*c"比较结果是对的，但万一出现"a*aa"和"aa*a"这种情形，直接比字符串会有隐患，因为分隔符*和字母的 ASCII 顺序可能干扰比较。干脆把字符串拆回变量数组，先按数组长度比，也就是 degree 降序；长度相同再逐个比较变量字符串。

List<Map.Entry<String, Long>> items = new ArrayList<>(poly.terms.entrySet()); items.sort((x, y) -> { String[] vx = x.getKey().isEmpty() ? new String[0] : x.getKey().split("\\*"); String[] vy = y.getKey().isEmpty() ? new String[0] : y.getKey().split("\\*"); if (vx.length != vy.length) { return vy.length - vx.length; } for (int i = 0; i < vx.length; i++) { int cmp = vx[i].compareTo(vy[i]); if (cmp != 0) { return cmp; } } return 0; });

这段代码有个细节值得说：如果两项的变量组合相同，说明它们是同一个 key，在terms里早被addTerm合并了，不可能同时出现在遍历结果里。所以 comparator 走到最后的return 0只是一种防御式写法，实际不会触发。

4.2 输出格式的三种分支

排序结束后，要把每一项拼成字符串。根据 key 是否为空，走两种完全不同的拼接方式：

List<String> formatResult(Poly poly) { List<Map.Entry<String, Long>> items = new ArrayList<>(poly.terms.entrySet()); items.sort(...); // 上面的 comparator List<String> ans = new ArrayList<>(); for (Map.Entry<String, Long> e : items) { long coeff = e.getValue(); if (coeff == 0) { continue; } String key = e.getKey(); if (key.isEmpty()) { ans.add(String.valueOf(coeff)); } else { ans.add(coeff + "*" + key); } } return ans; }

这里的coeff + "*" + key写法虽然简单，却能同时处理正负系数：

• 系数是-2，key 是"a*b"，拼出来是"-2*a*b"。
• 系数是1，key 是"e"，拼出来是"1*e"。
• 系数是-1，key 是"a"，拼出来是"-1*a"。

注意输出格式要求系数1必须写出来，所以不能像数学课本那样省略。纯常数项则直接转字符串，不能加*。

4.3 本地验证用例表：看着答案调，比看报错更快

这种题最怕“不知道正确答案长什么样”。我整理了几个本地验证过的用例，每一组都能覆盖一种常见错误：

最后一个用例很巧妙：(a + b) * a展开是a*a + a*b，后面减掉的正好也是a*a + a*b，两边抵消成 0，所以返回空列表。这是检验“系数为 0 的项必须删除”的极佳用例。

(a + x) * (b - x)在x = 2时，先替换再展开：(a + 2) * (b - 2) = a*b - 2a + 2b - 4。排序后 degree 为 2 的a*b在最前，degree 为 1 的两项中a字典序小于b，常数-4垫底。

5. 复盘“豆包题”：我实际调试时反复踩的坑

5.1 五个翻车现场和它们对应的修改

第一坑是变量替换时机。我前面已经讲过多遍，这里不再展开，只强调一句：在 parseFactor 读到变量时立刻替换，是最安全的方案。

第二坑是 key 不排序。我第一次写combineKey时直接a + "*" + b，没排序，结果a*b和b*a被当成两项，输出里出现了重复变量组合的不同顺序。这个问题在只有一个乘法时看不出来，一旦表达式变长就非常明显。后来我在combineKey里加Arrays.sort(all)，同类项合并立刻恢复正常。

第三坑是 comparator 写反。我最初先比较字典序再比较 degree，结果遇到a*a*b和a*b*b时，两项 degree 相同，变量序列逐位比较能分出先后；但遇到a*a*a和a*b时，我按字典序把a*b排到了前面，而题目要求先按 degree 降序，正确顺序应该是a*a*a在前。这个错误隐蔽在简单用例里，直到我用"a*a*a + a*b"做测试才暴露。

第四坑是常数项为 0 没有删除。addTerm里虽然写了terms.remove(key)，但sub里我最初用terms.put(key, -value)而不是addTerm，导致a - a化简后 map 里残留"" -> 0，输出阶段判空时没排除它，最后吐出一个"0"。后来统一改用addTerm处理系数的合并和删除，问题消失。

第五坑是split("\\*")对空字符串的处理。常数项的 key 是空串，直接split("\\*")会返回一个长度为 1、内容是空串的数组，导致 comparator 里把常数项误判成 degree 为 1 的变量项。我在排序前加了key.isEmpty()判断，把常数项转成长度为 0 的数组，才彻底解决。

5.2 完整参考代码（Java）

整道题合在一起，核心部分并不算长。去掉注释，大概 130 行左右。完整结构如下：

class Solution { int pos; String s; Map<String, Long> evalMap = new HashMap<>(); public List<String> basicCalculatorIV(String expression, List<String> evalvars, List<Integer> evalints) { for (int i = 0; i < evalvars.size(); i++) { evalMap.put(evalvars.get(i), (long) evalints.get(i)); } s = expression.replace(" ", ""); pos = 0; Poly result = parseExpr(); return formatResult(result); } Poly parseExpr() { Poly cur = parseTerm(); while (pos < s.length() && (s.charAt(pos) == '+' || s.charAt(pos) == '-')) { char op = s.charAt(pos); pos++; Poly rhs = parseTerm(); if (op == '+') cur = Poly.add(cur, rhs); else cur = Poly.sub(cur, rhs); } return cur; } Poly parseTerm() { Poly cur = parseFactor(); while (pos < s.length() && s.charAt(pos) == '*') { pos++; cur = Poly.mul(cur, parseFactor()); } return cur; } Poly parseFactor() { if (s.charAt(pos) == '(') { pos++; Poly inner = parseExpr(); pos++; return inner; } if (Character.isDigit(s.charAt(pos))) { long val = 0; while (pos < s.length() && Character.isDigit(s.charAt(pos))) { val = val * 10 + (s.charAt(pos) - '0'); pos++; } return new Poly(val); } int start = pos; while (pos < s.length() && (Character.isLetter(s.charAt(pos)) || Character.isDigit(s.charAt(pos)))) { pos++; } String var = s.substring(start, pos); if (evalMap.containsKey(var)) { return new Poly(evalMap.get(var)); } Poly p = new Poly(); p.addTerm(var, 1); return p; } List<String> formatResult(Poly poly) { List<Map.Entry<String, Long>> items = new ArrayList<>(poly.terms.entrySet()); items.sort((x, y) -> { String[] vx = x.getKey().isEmpty() ? new String[0] : x.getKey().split("\\*"); String[] vy = y.getKey().isEmpty() ? new String[0] : y.getKey().split("\\*"); if (vx.length != vy.length) return vy.length - vx.length; for (int i = 0; i < vx.length; i++) { int cmp = vx[i].compareTo(vy[i]); if (cmp != 0) return cmp; } return 0; }); List<String> ans = new ArrayList<>(); for (Map.Entry<String, Long> e : items) { long coeff = e.getValue(); if (coeff == 0) continue; String key = e.getKey(); if (key.isEmpty()) { ans.add(String.valueOf(coeff)); } else { ans.add(coeff + "*" + key); } } return ans; } static class Poly { Map<String, Long> terms = new HashMap<>(); Poly() {} Poly(long constVal) { if (constVal != 0) terms.put("", constVal); } void addTerm(String key, long coeff) { terms.merge(key, coeff, Long::sum); if (terms.get(key) == 0) terms.remove(key); } static Poly add(Poly a, Poly b) { Poly res = new Poly(); res.terms.putAll(a.terms); for (Map.Entry<String, Long> e : b.terms.entrySet()) { res.addTerm(e.getKey(), e.getValue()); } return res; } static Poly sub(Poly a, Poly b) { Poly res = new Poly(); res.terms.putAll(a.terms); for (Map.Entry<String, Long> e : b.terms.entrySet()) { res.addTerm(e.getKey(), -e.getValue()); } return res; } static Poly mul(Poly a, Poly b) { Poly res = new Poly(); for (Map.Entry<String, Long> e1 : a.terms.entrySet()) { for (Map.Entry<String, Long> e2 : b.terms.entrySet()) { res.addTerm(combineKey(e1.getKey(), e2.getKey()), e1.getValue() * e2.getValue()); } } return res; } static String combineKey(String k1, String k2) { if (k1.isEmpty()) return k2; if (k2.isEmpty()) return k1; String[] v1 = k1.split("\\*"); String[] v2 = k2.split("\\*"); String[] all = new String[v1.length + v2.length]; System.arraycopy(v1, 0, all, 0, v1.length); System.arraycopy(v2, 0, all, v1.length, v2.length); Arrays.sort(all); return String.join("*", all); } } }

5.3 如果只能记住三件事

第一，替换 evalvars 要趁早。解析到变量 token 时就查表，别等展开完再想怎么回代。

第二，key 一定要排好序再合并。变量连乘串不排序，同类项就永远合并不干净，排序规则再对也白搭。

第三，输出前过滤系数为 0 的项，常数项 key 为空时单独处理。这两条看着是边角料，实际上决定了你能不能通过样例。

我自己做完这题之后，最大的感受是：这类“表达式展开”题，考的不是某个偏门算法，而是把一个复杂问题拆成“解析、运算、排序”三个独立模块的工程感。每个模块都不难，难的是在动手前把模块边界想清楚。如果在面试里遇到它，哪怕最后没写出全部代码，只要能把这一段思路讲完整，面试官通常也会很满意。