北京一大厂员工被裁，拿到了56万赔偿。其媳妇太兴奋，在某平台发图分享喜悦，结果截图里公司名称没打码。

刚刷到这个，真给我看懵了。

北京一大厂员工被裁，拿了56万赔偿，本来算是安全落地。结果媳妇太激动，直接发网上炫，截图里公司名都没打码。

等反应过来删帖，已经晚了，网友截图到处传，公司、部门、姓名全被扒出来了。

这下钱是拿到了，社死也直接拉满。同事估计一眼就认出来，HR看完都得沉默。高兴归高兴，这种东西是真不能往网上扔啊。

今日算法题

标签验证器：这题用正则写，后面大概率会把自己绕进去

是合法代码，但不合法。

标签看着都闭合了，为什么第二段不行？因为整个字符串只能有一个根标签。标签验证器麻烦的地方不在括号匹配，而在于普通标签、结束标签和 CDATA 混在了一起。

这题我第一眼不会上正则。正则处理单层格式还凑合，一碰到嵌套标签，表达式很快就会变成一团没人敢改的东西。老老实实从左往右扫描，再用一个栈记录没有闭合的标签，反而更稳。

扫描时主要盯住三种内容：

遇到，校验标签名后压栈；遇到，检查它是不是栈顶标签；遇到<![CDATA[，直接找到最近的]]>，中间内容全部跳过。

CDATA 这里容易写错。它里面出现、都只是普通字符，不能继续当标签解析。而且 CDATA 不能跑到根标签外面，下面这种写法直接判错：

Java 实现我会这样写：

import java.util.ArrayDeque;

import java.util.Deque;

publicclass TagValidator {

  public boolean isValid(String code) {

      if (code == null || code.isEmpty()) {

          returnfalse;

      }

      Deque<String> openedTags = new ArrayDeque<>();

      boolean rootStarted = false;

      int cursor = 0;

      while (cursor < code.length()) {

          // 根标签已经结束，后面还有字符，说明出现了第二个根节点

          if (rootStarted && openedTags.isEmpty()) {

              returnfalse;

          }

          if (code.startsWith("<![CDATA[", cursor)) {

              if (openedTags.isEmpty()) {

                  returnfalse;

              }

              int cdataEnd = code.indexOf("]]>", cursor + 9);

              if (cdataEnd < 0) {

                  returnfalse;

              }

              cursor = cdataEnd + 3;

              continue;

          }

          if (code.startsWith("</", cursor)) {

              int closeBracket = code.indexOf('>', cursor + 2);

              if (closeBracket < 0) {

                  returnfalse;

              }

              String tagName = code.substring(cursor + 2, closeBracket);

              if (!legalTagName(tagName)) {

                  returnfalse;

              }

              if (openedTags.isEmpty()

                      || !openedTags.peek().equals(tagName)) {

                  returnfalse;

              }

              openedTags.pop();

              cursor = closeBracket + 1;

              continue;

          }

          if (code.charAt(cursor) == '<') {

              int closeBracket = code.indexOf('>', cursor + 1);

              if (closeBracket < 0) {

                  returnfalse;

              }

              String tagName = code.substring(cursor + 1, closeBracket);

              if (!legalTagName(tagName)) {

                  returnfalse;

              }

              openedTags.push(tagName);

              rootStarted = true;

              cursor = closeBracket + 1;

              continue;

          }

          // 普通文本必须待在某个标签内部

          if (openedTags.isEmpty()) {

              returnfalse;

          }

          cursor++;

      }

      return rootStarted && openedTags.isEmpty();

  }

  private boolean legalTagName(String name) {

      if (name.isEmpty() || name.length() > 9) {

          returnfalse;

      }

      for (int i = 0; i < name.length(); i++) {

          char ch = name.charAt(i);

          if (ch < 'A' || ch > 'Z') {

              returnfalse;

          }

      }

      returntrue;

  }

}

这段代码里有两个判断不能省。

一个是标签名只能由 1 到 9 个大写英文字母组成，和都不合法。另一个是栈空之后不能继续扫描，否则会被误判成两个各自正确的标签。

整套扫描没有回头处理字符，时间复杂度是O(n)。栈里保存的是当前尚未闭合的标签，最坏空间复杂度也是O(n)。

这题真正考的不是会不会用栈，而是扫描顺序。CDATA 必须放在普通开始标签之前判断，结束标签也得单独处理。顺序写乱了，代码表面没报错，碰到<![CDATA[这种输入时就开始误解析，这种问题比算法本身更难查。