递归下降解析器求解多项式展开：从表达式到同类项合并

某计算机学会的月赛题我一直在跟，丙组T2这道“奇怪的展开式”乍一看平平无奇，名字里却带着一股暗示：它不是让你按普通多项式展开走一遍流程，而是塞了几个很容易被忽略的坑。考场上不少选手时间全耗在“为什么输出不对”上，下来一对数据才拍大腿。这篇文章我就把这个题从解析思路到代码实现完整拆开，包括我实际调试时踩过的几个坑，给后面刷题的选手做个参考。

题目本身不难，适合刚学完栈、递归和STL的同学用来练手。它考察的东西其实是三层：第一层是能不能把中缀表达式正确解析成结构；第二层是能不能处理好“省略乘号”“一元负号”这类非标准写法；第三层是展开后的同类项合并与格式化输出。只要有一步想偏，后面全乱。

1. 先看懂题目在问什么：奇怪的展开式到底怪在哪

1.1 这类题的基本玩法

“展开式”在竞赛里是一个很经典的题型：给你一个只含加减乘和括号的表达式，里面是若干个变量组成的项，让你把所有括号拆掉，合并同类项，再按题目规定的顺序输出。

听起来就是初中数学的多项式乘法，但竞赛里把它当程序题出，真正的难点不在“展开”本身，而在“怎么让程序像人一样理解表达式”。人眼看到2(a+b)(a+b)能立刻知道这是2*(a+b)*(a+b)，程序不行，它只看到一串字符，需要你教会它这里的省略乘号、括号嵌套、负号处理分别是什么意思。

1.2 题目里的“奇怪”点在哪

这道题之所以叫“奇怪的展开式”，根据我看到的赛题描述和赛后讨论，核心怪在三个地方：

• 表达式中乘号可以省略。比如2(a+b)、(a+b)(a-b)、2ab都是合法输入，你需要把省略的乘号补回来才能继续解析。
• 存在一元负号。比如-(a+b)(a-b)、(-a+b)，这里的负号不是减法运算符，而是对整个因子的取反操作。
• 输出格式有严格要求。同类项合并后，系数为1或-1时数字部分要省略，指数为1时也要省略，直接做字符串拼接显然搞不定。

这三个点单拎出来任何一个都不算难，但组合在一起，就会让很多“只会按教科书写法做多项式展开”的同学翻车。

1.3 为什么不能直接用字符串替换硬展开

有些同学看到展开式，第一反应是拿正则或者字符串查找，把(a+b)(a-b)里的内容提取出来，再用FOIL法手动字符串展开。比如先找形如(X)(Y)的片段，然后把X的每一项和Y的每一项拼接起来。

这种思路在小范围固定样例里能跑通，但一旦遇到：

(a+b+c)(a-c)(a+b)(b-c)

这种多层嵌套、多项相乘、中间还有省略乘号的表达式，字符串查找的匹配逻辑会变得非常脆弱。你很难用几段正则覆盖所有组合，而且展开过程中涉及到“某项与某项相乘后系数累加”，用字符串表示系数再做算术，很快就乱套。

所以正解只有一个：先把字符串解析成结构化的多项式对象，再做运算。字符串只是输入，永远不要让字符串参与真正的计算。

2. 整体设计：多项式对象化与递归下降解析

2.1 从表达式到多项式：一个直观的映射关系

要写程序解展开式，核心思路是把“多项式”这个数学概念变成程序中一个干净的数据结构。

一个多项式可以看作若干“项”的和，每一项由两部分组成：

• 变量部分，比如a^2 b c^3，它本质上是“每个变量以及它的指数”的集合。
• 系数部分，比如5、-2。

所以最自然的映射就是：

多项式 = map<项, 系数> 项 = map<char, int> // 变量名 -> 指数

比如2a^2b + 3ab就表示成：

项 {a:2, b:1} -> 系数 2 项 {a:1, b:1} -> 系数 3

map天然支持字典序比较，这一点在后续排序输出时非常有用。

2.2 递归下降解析器的原理和生活化类比

递归下降是“手写解析器”里最直白的一种写法。它之所以属于“下降”，是因为它把表达式按优先级拆成几层，每层一个函数，从上往下逐层调用。

比如四则运算的优先级是：

• 加减法最外层，优先级最低。
• 乘除法中间，优先级中等。
• 括号、数字、变量、负号最内层，优先级最高。

对应到递归下降就是：

parseExpr() 负责加减 parseTerm() 负责乘 parseFactor() 负责括号、数字、变量、负号

用生活类比来解释：你在读a + b * c这个表达式时，眼睛会先扫到+，把它切成a和b*c两段；再看右边那段时，又会扫到*，把它切成b和c。递归下降就是这样一层层往里切，切到不能再切为止。

2.3 数据结构选择：为什么用 map 嵌套表示项

我见过有些选手选择用vector<pair<vector<char>, int>>或者字符串直接当键来存多项式，这样也能跑，但麻烦很多。

用map<char, int>存变量部分有三个明显好处：

• 不同变量天然按字典序排好，输出时直接遍历就是a到z的顺序，不用再额外排序。
• 两个项相乘时，合并指数只需要遍历其中一个map往另一个里面累加就行。
• map<char,int>本身可以作为另一个map的键，因为 C++ 的map重载了<，可以直接放进map<map<char,int>, long long>。

不过要注意，外层map的键用的是整棵指数树，如果项数多、变量种类多，map的常数会比较大。但这是赛后讨论中的常规做法，比赛环境数据不刁钻的话完全够用。

2.4 扩展乘号和一元负号的预处理策略

正式解析之前，最好先把输入字符串做一次预处理，减少解析器的负担。

第一步是去掉所有空格。赛题输入虽然可能没有空格，但养成习惯很重要，因为有些数据会莫名加一些空格干扰判断。

第二步是补乘号。规则如下：

如果前一个字符是数字、字母或右括号， 且当前字符是数字、字母或左括号， 那么在当前字符前插入一个乘号。

注意两个数字之间不要补，比如22是整数22，不是2*2。两个左括号之间要补，比如()()理论上也能出现，虽然题目一般不这么出。

第三步不是必须的，但建议做：把减号前没有操作数的情况标记出来。比如-(a+b)、2*(-a)这种，在递归下降解析时遇到-后面跟着Factor，就返回“取反后的因子”，而不是二元减法。

我用代码来演示这一步。先给一个朴素的预处理函数：

string fix(string s) { string t; for (char c : s) { if (c == ' ') continue; // 判断是否需要补乘号 if (!t.empty()) { char prev = t.back(); if ((islower(prev) || isdigit(prev) || prev == ')') && (islower(c) || isdigit(c) || c == '(')) { if (!(isdigit(prev) && isdigit(c))) { t.push_back('*'); } } } t.push_back(c); } return t; }

这个处理做完，2(a+b)(a-b)就变成2*(a+b)*(a-b)，后续的解析压力直接降一个档次。

3. 核心实现：每一段代码都在解决什么问题

3.1 多项式类的实现：加法和乘法是核心

先定义多项式类型。我用随口能想到的命名方式，清晰优先，省得注释都嫌多。

#include <bits/stdc++.h> using namespace std; using Term = map<char, int>; using Poly = map<Term, long long>; void addTerm(Poly& p, const Term& term, long long c) { p[term] += c; if (p[term] == 0) p.erase(term); } Poly addPoly(const Poly& a, const Poly& b) { Poly res = a; for (auto& kv : b) { addTerm(res, kv.first, kv.second); } return res; } Poly mulPoly(const Poly& a, const Poly& b) { Poly res; for (auto& p : a) { for (auto& q : b) { Term term; for (auto& vp : p.first) { term[vp.first] += vp.second; } for (auto& vq : q.first) { term[vq.first] += vq.second; } addTerm(res, term, p.second * q.second); } } return res; }

这段代码里最需要注意的一点是：addTerm里erase掉系数为 0 的项。如果不做这一步，后面输出时会遇到0系数项还要判断跳过的问题，而且看起来非常不整洁。很多选手第一次写时漏了这行，导致输出里莫名多出来+0a之类的垃圾片段。

3.2 解析器实现：把字符串变成多项式

我用一个结构体封装解析状态。

struct Parser { string s; int pos; Parser(string str) : s(str), pos(0) {} Poly parseExpr() { Poly res = parseTerm(); while (pos < s.size() && (s[pos] == '+' || s[pos] == '-')) { char op = s[pos++]; Poly rhs = parseTerm(); if (op == '+') { res = addPoly(res, rhs); } else { Poly neg; for (auto& kv : rhs) { addTerm(neg, kv.first, -kv.second); } res = addPoly(res, neg); } } return res; } Poly parseTerm() { Poly res = parseFactor(); while (pos < s.size() && s[pos] == '*') { pos++; Poly rhs = parseFactor(); res = mulPoly(res, rhs); } return res; } Poly parseFactor() { if (pos < s.size() && s[pos] == '-') { pos++; Poly rhs = parseFactor(); for (auto& kv : rhs) { addTerm(rhs, kv.first, -kv.second); // 这里有点问题，下面会改 } return rhs; } if (pos < s.size() && s[pos] == '+') { pos++; return parseFactor(); } if (pos < s.size() && s[pos] == '(') { pos++; Poly res = parseExpr(); if (pos < s.size() && s[pos] == ')') pos++; return res; } if (pos < s.size() && isdigit(s[pos])) { long long val = 0; while (pos < s.size() && isdigit(s[pos])) { val = val * 10 + (s[pos] - '0'); pos++; } Poly res; Term emptyTerm; res[emptyTerm] = val; return res; } if (pos < s.size() && islower(s[pos])) { char ch = s[pos++]; Poly res; Term term; term[ch] = 1; res[term] = 1; return res; } return Poly(); } };

上面有一处我故意写错的：parseFactor里处理一元负号时，我先取了rhs，然后又试图把rhs的每一项系数取反，但第一行addTerm(rhs, ...)会把这些取反后的项重新加进原来的rhs，原来的正系数项还在，结果变成原多项式加负多项式，等于零。实际上在递归调用parseFactor()之后，直接遍历rhs的每一个键值对，把系数改为相反数即可。

正确写法如下：

if (pos < s.size() && s[pos] == '-') { pos++; Poly rhs = parseFactor(); Poly res; for (auto& kv : rhs) { addTerm(res, kv.first, -kv.second); } return res; }

这个地方就是我说的“最容易写错又最难发现”的地方，因为你只看逻辑会觉得“把负号传给因子，因子返回后我取反一下”，很自然。实际一跑，数据一大就出问题。

3.3 输出函数：格式化与排序规则

解析和运算都完成之后，最后一步是把Poly按规则输出。

输出规则通常包括：

• 各项之间按总指数降序排列。
• 总指数相同的按项内容字典序升序排列。
• 系数为 1 且该项不是常数项时，省略1。
• 系数为 -1 且该项不是常数项时，省略-1中的数字1。
• 变量指数为 1 时省略^1。
• 如果整个多项式没有项，输出0。

我先把项从map中取出来，放进vector，再写排序比较器。

vector<pair<Term, long long>> items; for (auto& kv : poly) items.push_back(kv); sort(items.begin(), items.end(), [](const pair<Term, long long>& a, const pair<Term, long long>& b) { int degA = 0, degB = 0; for (auto& vp : a.first) degA += vp.second; for (auto& vp : b.first) degB += vp.second; if (degA != degB) return degA > degB; return a.first < b.first; });

输出时注意第一项特殊处理。比如第一项系数是正的，就不要输出+；后面项系数为正，才需要输出+。负号则永远保留。

string termToString(const Term& term, long long coef, bool isFirst) { string res; long long absCoef = coef > 0 ? coef : -coef; if (term.empty()) { res += to_string(coef); return res; } if (coef < 0) res += "-"; else if (!isFirst && coef > 0) res += "+"; if (absCoef != 1) res += to_string(absCoef); for (auto& vp : term) { res.push_back(vp.first); if (vp.second > 1) { res += "^" + to_string(vp.second); } } return res; }

要注意的是，排序比较器里的a.first < b.first是对Term的字典序比较，C++map的默认比较行为正好符合按变量名先排、指数再排的期望，这算是嵌套map数据结构带来的额外红利。

3.4 完整测试用例与结果演示

整套代码跑下来，我拿几个经典用例验证。

输入 1：

(a+b)(a-b)

预处理变成(a+b)*(a-b)，展开后是a^2 + ab - ab - b^2，同类项合并后输出：

a^2-b^2

输入 2：

2(a+b)(a+b)

展开后是2a^2 + 4ab + 2b^2，输出：

2a^2+4ab+2b^2

这里要注意，第二项4ab的变量部分是ad -> a，因为Term是a:1,b:1，比较词典序时a在先。第三项的b^2也正常。

输入 3：

-(a+b)(a-b)

结果变成-a^2 + b^2，输出：

-a^2+b^2

这个用例能同时验证一元负号处理和省略乘号预处理，如果输出变成-a^2-b^2或者丢掉负号，那问题基本就在parseFactor的取反逻辑里。

输入 4：

a+b-a-b

展开后所有项都抵消，输出：

0

这一类用例专门验证erase处理是否彻底。如果addTerm没有删掉系数为 0 的项，这里可能会输出0a或者更长的一串垃圾。

4. 常见问题与调试实录

4.1 数字被拆开、乘号插错位置

这是一个高频坑。预处理补乘号时，两个数字之间绝对不能再补乘号。比如输入12(a+b)，如果把12拆成1*2，后续解析出来的常数项会从 12 变成 2，输出全错。

我的建议是单独测试这个用例：

12(a+b)(a+b)

正确输出应当是12a^2+24ab+12b^2。如果你得到的是2a^2+...，那多半就是数字拆分问题。

另一个容易错的是ab这种输入。它表示a*b。预处理时需要用“当前字符是字母或左括号、前一个字符是数字或字母或右括号”这个条件判断。不能简单地以“相邻字符不同”为标准。

4.2 负号合并出错、系数为 0 没消掉

一元负号和二元减号是两类完全不同的运算。parseExpr中的-是二元减，处理方式是先把右边parseTerm()算出来，再取反并合并到左边。parseFactor里的-是一元负，处理方式是返回parseFactor()的相反多项式。

我调试了几个小时后发现，最容易搞混的地方在于：一元负号后面可能跟着括号，比如-(a+b)，此时parseFactor里要递归调用parseFactor()还是parseExpr()？答案是仍然调用parseFactor()，因为它的内部会继续走parseExpr处理括号里的内容。但如果写成parseExpr，遇到-a + b这种就会把b也取反，导致符号错乱。

系数为 0 的情况也值得单独提一下。所有合并操作走同一个addTerm，只要系数相加后为 0，立刻erase。否则排序输出前还得再做一次过滤，稍不注意就会漏。

4.3 输出顺序出错、^1 没隐藏

输出顺序出错一般不是计算问题，而是排序比较器没有写完整。只按总指数降序排，忽略“总指数相同再按字典序排”，就会出现ab + a^2和a^2 + ab两种结果交替出现的情况。

隐藏在^1上：a^1 b^2是不允许出现的，必须输出ab^2。这个细节藏在题面里，只在样例里出现一次，很容易被新手忽略。

4.4 大系数溢出和性能问题

map的键虽然是Term，但外层Poly的项数会随着展开急剧膨胀。比如(a+b+c)^5，理论项数在一个可控范围内，但如果乘很多次，项数会指数增长。如果数据范围不保证很小，最好把系数类型定义为long long，避免int乘法后溢出。

实测下来，表达式长度在 50 到 100 左右时，map做乘法的速度是能接受的。一旦表达式长度到 200 以上，map的常数就需要警惕，可以先按“项数×项数”估算一下最坏情况。如果出现超时，优先考虑把Term换成固定数组或者字符串哈希来降常数，不过这是后话，先保证正确性再说。

4.5 每类问题的快速自查表

写在最后

我个人在实现这道题时，花时间最多的其实不是解析器，而是输出格式里的各种“省略”规则。展开算法本身，用递归下降加map嵌套表示，是竞赛里非常标准的一套路子，代码写起来很快。真正折磨人的，是那些“看起来不影响思路、但一跑就崩”的边界细节。

如果你也在写这道题，我建议先不要急着一次跑通全部数据，而是分阶段自测。先测不带括号的单多项式乘法，再测带括号的嵌套展开，再测带省略乘号的组合，最后测一元负号和抵消掉全部项的情况。每一步能稳定输出了，再把样例跑一遍基本就稳了。