说实话我最初翻到 UVa 11484 Document Object Model 这道题时先愣了一下UVa 不是搞算法竞赛的老牌题库吗怎么把浏览器前端的 DOM 概念搬上来了等我把题面读完才反应过来它考的压根不是浏览器、不是 JavaScript、也不是 CSS而是给你一段类似 HTML 的标记语言文本让你自己实现一个简化版的“文档对象模型”解析器把文本转换成树结构再按题目要求去遍历、查询、输出。换句话说这是一道非常典型的“模拟 树结构”题属于那种看起来唬人、想清楚之后就剩下码量的类型。这篇文章我打算用完整复盘的方式讲清楚我从拆题、词法分析、建树、遍历到最终调试的全过程。不是贴一份 AC 代码就完事而是把每一步为什么这么设计、哪些地方容易翻车、怎么构造测试数据都讲透。如果你正在刷 UVa 系列或者准备面试时遇到“手写一个简单 HTML 解析器”这类题这篇东西应该能帮你少走不少弯路。1. 拆题DOM 题在 ACM 里到底在考什么1.1 浏览器里的 DOM 和算法题里的“假 DOM”先聊一个容易混淆的问题。我们在前端说的 DOM是浏览器把 HTML 文档解析成一棵对象树然后提供document.getElementById、parentNode、childNodes这一整套 API 给脚本操作页面。它的背后是一套极其复杂的 HTML5 解析算法包含容错处理、标签自动补全、乱写也能猜出结构的“宽松模式”。那套东西别说 ACM就算让浏览器团队里的人手工实现一遍也不是一晚上能干完的事。UVa 这道所谓的 Document Object Model和浏览器里的真 DOM 只保留了最核心的骨架把一段文本中的标签和内容组织成树然后让节点带上“父亲是谁、孩子有哪些、在第几层”这些信息。输入多数是良构的不需要你像浏览器那样去修正p没闭合的问题标签种类也就比真实 HTML 少得多甚至可能只是十几个自拟的标记名称。为什么 ACM 要出这种题因为它考察的不是你能不能背出 DOM API而是字符串处理的细致程度尤其是词法分析阶段树结构的建模以及建树的时机和边界条件遍历方式的选型是先序、层序还是后序复杂度是否可控。一个题名带 “Document Object Model” 的题目本质上和三年前那批“表达式括号匹配”“XML 解码器”是同一类东西。想明白这一点你的心态就会从“我没写过浏览器”变成“这不就是一个带标签的括号匹配吗”。1.2 我把题意拆成了三个子任务刷题的时候我习惯先画一条任务链把抽象的题面翻译成可以动手的子任务。UVa 11484 按我读题后的理解可以拆成这三段词法分析把原始字符串拆成“开始标签”“结束标签”“自闭合标签”“文本”四类 Token树构建用栈维护当前嵌套深度把 Token 流变成一棵多叉树查询与输出根据题目要求在这棵树上做对应顺序的遍历并按格式打印。这套三段式看起来平平无奇但它涵盖了这类解析题 90% 的工作量。我见过不少选手在第一步就走偏比如用正则去匹配 HTML 标签结果遇到属性值里的直接当场去世也有选手跳过 Token 流直接边读字符边建树最后代码里塞满了奇怪的状态分支改一个 bug 又崩出三个新 bug。我的建议永远不变宁可多开一个数组、多写一个循环也要把阶段拆干净。很多 WA 的根源不是不会建树而是词法那一步已经吞错了字符。2. 词法分析先把字符串嚼碎成 Token2.1 边扫描边切不要迷信正则词法分析的目标是把原始文本切成一串 Token。比如下面这行输入div classboxhellobr/world/div在我这里应该被切成开始标签div classbox文本hello自闭合标签br/文本world结束标签/div实现上最简单的方式是维护一个i指针逐个字符往后扫。遇到就进入“标签态”一直扫到匹配的为止把中间整段作为标签 Token遇到普通字符就进“文本态”累积到下一个前为止。核心代码大概长这样vectorstring tokenize(const string s) { vectorstring tokens; int i 0, n s.size(); string cur; while (i n) { if (s[i] ) { if (!cur.empty()) { tokens.push_back(cur); cur.clear(); } int j i 1; while (j n s[j] ! ) j; tokens.push_back(s.substr(i, j - i 1)); i j 1; } else { cur.push_back(s[i]); i; } } if (!cur.empty()) tokens.push_back(cur); return tokens; }为什么我不建议用正则因为如果输入是多行大文本正则要么写得很长要么在某些字符集下性能退化而手动扫一遍的复杂度就是O(n)清晰可控。这里n是全文长度。如果你担心while (j n s[j] ! )没处理引号里的那你的担心非常正确——这正是我一直强调的坑下面细说。2.2 属性字符串最容易写脏的地方在标签 Token 里真正影响树结构的是标签名也就是div classbox里的div因为这是节点在树上的名字。属性名和属性值通常只是“附带信息”题目让你保留就保留不让你输出就可以不存。但不管存不存你都必须在扫描标签内容时正确跳过它们否则就会犯一个低级错误把判断成标签结束而被它截断的其实只是属性值的一部分。想象一下这段输入a titleabclick/a如果你用朴素的“扫描到就结束”逻辑标签会在b的处提前截断。这显然不对因为前后有双引号包裹属于属性值的一部分。正确的标签式扫描必须维护一个inQuote标志遇到双引号或单引号就翻转状态只有在非引号状态下的才是 Tag 的真正结束。int j i 1; bool inQuote false; while (j n) { if (s[j] || s[j] \) inQuote !inQuote; else if (s[j] !inQuote) break; j; }这个修正是阿里 P8 面试都爱问的细节放在 ACM 里就是一道题的 AC 分水岭。我第一版交上去 WA查了很久才发现属性值里有个带的字符串从那之后我对“引号保护”变得格外敏感。2.3 自闭合标签与空白文本的预处理HTML 里有一堆天然不带结束标签的空元素比如br、img、hrXHTML 写法会在末尾加/也就是br/。算法题里面为了简化一般统一用br/这种带自闭合标记的形式。我判断自闭合的方法很简单去掉末尾之后如果字符串最后一个字符是/它就是一个自闭合标签。bool isSelfClose(const string tk) { return tk.size() 2 tk[tk.size() - 2] /; }注意这里有个坑tag /这种带空格的写法最后一个/前面有空格但取tk[tk.size() - 2]仍然能得到/因为空格在/前面/仍然紧挨着。只有当标签写成了tag / 这种完全离谱的格式时才会判断失效而题目基本不可能出这种数据。空白文本要不要作为节点建进树里我一开始的做法是“照单全收”结果输出格式总是多出莫名其妙的空行。后来改成规则更稳如果一个文本 Token 去掉首尾空格后是空串直接丢弃否则保留原文本或者按题面要求进行 trim。真实 DOM 里空白文本其实是会生成#text节点的但 ACM 题目通常只关心有实际内容的文本否则输出根本没法看。这条规则看起来简单实际能避免大量“输出和答案差一个换行”的经典 WA。3. 建树用栈把 Token 拼成父子关系3.1 栈就是那个“当前父节点”指针Token 流接好了下一个问题是怎么把一串平坦的标签序列变成树这里要借用一个老生常谈的数据结构——栈。它的作用非常自然栈顶永远表示“当前正在处理哪个节点新来的平级内容应该挂到谁下面”。你可以把这种嵌套结构类比成一个文件夹目录。你进入一个目录就把它压入栈你在目录里新建文件文件就属于当前栈顶目录你返回到上级目录就把栈顶弹出去。树遍历的回溯本质上是同一套逻辑只不过建树时不需要“回头”只需要按顺序处理 Token 就能一次性拼出全部父子关系。为什么栈能做到这一点因为标签嵌套天然具有后进先出的性质后开始的标签必须先结束先开始的标签后结束。这种“先进后出”的嵌套顺序正好和栈的语义完全对齐。你可以把开始标签当成(结束标签当成)那么建树过程本质上就是在做一个增强版括号匹配。3.2 三种 Token 对应的三种栈操作我用一个“虚拟文档根节点”作为树的根编号为 0标签名设为#document。它永远不会出栈这样无论是挂在最外层的文本还是顶层散落的标签都能找到一个统一归属。建树逻辑可以写成这样const int MAXN 100005; struct Node { string tag; int parent; vectorint children; } tree[MAXN]; int tot 0; // 当前节点总数 vectorint stk; stk.push_back(0); // 根节点先入栈 for (string tk : tokens) { if (tk[0] ! ) { // 文本 Token string text trim(tk); if (text.empty()) continue; int u tot; tree[u].tag #text; int p stk.back(); tree[u].parent p; tree[p].children.push_back(u); } else if (tk[1] /) { // 结束标签 stk.pop_back(); } else { // 开始标签或者自闭合标签 bool selfClose isSelfClose(tk); int u tot; tree[u].tag parseTagName(tk); int p stk.back(); tree[u].parent p; tree[p].children.push_back(u); if (!selfClose) stk.push_back(u); } }这里有一个细节值得划重点开始标签和自闭合标签的区别仅仅在于“是否入栈”。自闭合标签作为一个节点挂到父亲下面之后它的生命周期就结束了不需要压栈因为它不可能有子节点。如果看到div/它就是一棵没有孩子的枯树。文本 Token 的处理同理挂在栈顶父亲下之后同样不压栈。只有“可能产生子节点”的普通开始标签才需要入栈。3.3 非法嵌套、多余结束标签、未闭合标签怎么办理论上算法题会保证输入良构但实际写代码时绝不能赌这一点。我刷题时秉持一个原则走自己的解析逻辑遇到异常至少不能让程序 RE 或者死循环。比如多余结束标签如果栈里只有一个根节点此时stk.pop_back()会把根节点弹出后续所有节点都失去归属。我的防御做法是当stk.size() 1时才允许弹出否则忽略这个结束标签。未闭合标签输入结束时栈里还残留若干节点那这些节点就是嵌套没关完。Tree 结构本身已经建出来了它们依然挂在对应父亲下面所以输出可能不符合预期但不至于 RE。结束标签与开始标签不匹配比如ab/a/b严格来说应该是a/ab/b才对。遇到这种数据按栈弹出会得到错误的父子关系。题目如果保证了良构这个问题就不存在如果没有保证那就只能说明这道题的难度远不止模拟了。防御性代码不会让你的答案在正确数据上变慢只会在错误数据上救你一次。我那次被属性值里的坑了之后顺手把结束标签的弹出条件也改了之后就没再出现过越界问题。4. 查询与输出树建好之后才是真正的主菜4.1 为什么我坚持“先建树、再回答”有的选手会想既然输入边扫描边就能拿到深度那能不能一边解析一边输出答案省掉建树这一步短期看确实快但一旦题目要你回答的并非“当前深度”而是“两个节点的最近公共祖先”“某个节点的所有后代标签”“层序遍历结果”你就必须有一棵完整的树才能回答。而且边解析边输出会让代码耦合度爆炸——解析器的状态和查询逻辑混在一起调试时你分不清是哪个环节出了问题。所以我坚持一个原则解析阶段只负责建树查询阶段只负责读树。两阶段之间用一个数组传递信息。这样不仅好调试还顺带解决了多组数据清空的问题——每次重新初始化tot 0和根节点即可不需要动整棵树的残留内容。4.2 遍历方式与查询的对应关系树建好之后题目要的可能是一次简单的前序遍历输出标签名也可能要你处理若干次查询。不同遍历方式和问题类型之间有明确的对应关系问题类型推荐遍历方式原因按照文档顺序输出全部节点先序遍历DOM 的天然顺序就是“父在前子随后”输出每层有哪些节点层序遍历BFS层级关系和深度直接对应计算某个节点的深度/祖先链DFS 递归回溯递归天然携带祖先链两个节点之间的距离或公共祖先倍增 LCA 或 Tarjan需要预处理深度和跳转表统计某个子树的大小后序遍历先算清孩子再累加自己注意建树时我顺便记录parent这个看似多余的操作会在很多查询里救你一命。比如想知道深度不建树也能在解析时用depth depth[parent] 1直接算出来但如果题目在查询阶段才临时给你一个节点编号让你求它的深度你就必须能沿着parent一路回溯。所以parent字段别省。4.3 输出格式那些容易翻车的小地方Presentation Error是 UVa 的特色比 WA 更让人抓狂因为你的逻辑是对的但输出格式和答案差了那么一个空格。我在 UVa 11484 这道题上吃过三个输出相关的亏行尾多余空格很多遍历输出要求节点间用空格分隔但行尾不能有空格。稳妥做法是每行先判断是否是最后一个节点或者用一个first标志位只在两个元素之间输出空格。根节点要不要输出如果题目说“输出所有元素节点”那么#document这个虚拟根通常不输出。如果把根也打出来整棵树的结构会整体多一层。一定要在写代码前确认。文本节点的标签名我统一用#text表示有的题目叫TEXT有的干脆用原始文本内容。如果输出里出现了奇怪的#text而答案没有多半是题目根本不把文本当节点。多组数据的情况也要注意每轮 Case 结束之后栈要清空tot重建根节点要重新初始化。我最开始写的是“全局数组不清空、只改指针”结果第二组数据用到了第一组数据残留的 children直接 WA 一脸。5. 让代码从“样例过”到“AC”的调试过程5.1 先手工构造十个边界样例拿到一份能编译的代码后第一件事不是交题而是本地构造数据。我的做法是列一张检查清单把能想到的边界都测一遍测试场景输入期望验证点空文档空字符串或全是空白不能 RE输出空行或不输出单个标签a/a根下挂一个节点自闭合嵌套divbr//divbr 是 div 的子节点同层多个节点a/ab/ba、b 都是根节点直接子节点属性值带a titlexyt/a标签能被正确截断纯文本hello world文本挂在根下深层嵌套一百层a递归深度是否爆栈文本夹在标签之间pabb/bc/pa、b、c 的父子关系标签名大小写Div/Div是否按题意统一成小写空白文本p /p纯空白是否被丢弃这十个样例基本覆盖了这类题的 80% 边界。特别是“属性值带”那条没有它我根本发现不了引号解析的 bug。5.2 随机生成器 暴力对拍省掉几小时人肉验证手工样例只能验证主干逻辑真正的随机性测试要靠“对拍”。思路很简单写一个数据生成器随机生成合法的标记文本写一个暴力程序比如直接用递归建树再输出然后不停对比你的优化实现和暴力程序的输出一旦不一样就是 bug。生成器的小技巧是先随机生成一棵树再按先序把树“翻译”成带标签的文本这样能保证生成的输入一定是良构的。伪代码如下string genTree(int depth) { string res node to_string(rand() % 5) ; if (rand() % 2 depth 5) { res genTree(depth 1); } if (rand() % 3) res text to_string(rand() % 100); if (rand() % 2 depth 5) { res genTree(depth 1); } res /node to_string(rand() % 5) ; return res; }注意这里结束标签名要跟开始标签保持一致所以我简化成固定用和开始标签一样的名字。生成几千组数据用程序自动 diff 输出比人肉盯屏幕高效得多。我在争分夺秒做题时这套对拍流程不会超过十分钟但它能确保解决所有“隐藏边界”。5.3 性能、递归深度与读入优化UVa 这类老牌题目对时间复杂度要求不算苛刻但别掉进两个经典陷阱。第一递归爆栈。如果题目给了超深嵌套比如一百万个标签DFS 用递归很容易爆。解决办法是建树时就用depth[u] depth[parent] 1预先算好深度遍历时用显式栈模拟递归而不是调用系统递归。我在某道树上题吃过递归爆栈的亏从那之后凡是模拟建树的题我都默认“递归可能爆”。第二读入太慢。如果全文很长用cin且没有ios::sync_with_stdio(false)可能 TLE 在读入而不是算法上。我的标准做法是ios::sync_with_stdio(false); cin.tie(0); string input ; string line; while (getline(cin, line)) input line \n;注意如果用getline拼接每行之间的\n要保留否则文本 Token 会被错误拼接。我一开始图省事直接cin s读单词结果标签属性里的空格全被拆没了。这也是一个非常真实的坑。6. 从 UVa 11484 延伸开去这类解析题的通法写过这道题之后我明显感觉到自己面对“疑似解析题”的选择题速度快了很多。这里分享一个个人很受用的通法凡是题目名里带Parser、XML、HTML、Tree、DOM的题一律按“词法分析阶段 树构建阶段 查询遍历阶段”的三段式骨架来套。不需要每一题都从零开始想架构只需要调整每一段的细节内容词法阶段变化最多的是分隔符规则有的按括号切有的按标签切有的按空格切树构建阶段变化最少十有八九是栈或递归维护父子关系查询阶段变化最灵活但核心逃不出深度、祖先、子树、层序几种。还有一个很实用的判断标准如果一道题你看了十分钟还在想“这个 Token 流怎么切”说明词法规则没有彻底读懂此时应该回头再啃一遍题面而不是直接上手写代码。词法规则错了后面建树再漂亮也白搭词法规则对了建树和查询基本就是体力活。说了这么多其实核心观点就一句Document Object Model 这个名字吓不住人它的内核就是“标签嵌套的栈 树的遍历”。把字符串切干净把栈维护好把输出格式抠细AC 就是水到渠成的事。这套思路不只在 UVa 有效后来我遇到需要手写 JSON 解析器、实现一个简版 Markdown 渲染器的场景同样用同一套骨架十分钟内就能把代码组织起来——这才是这道题真正留给我的东西。