下面来说一下这个基于 DOM 的 Heading tree 解析程序的问题 #JS #Algorithm
你将学会如何在不使用显式递归的情况下，只用栈数据结构该如何解析提取嵌套结构

一个明显的好处是这么做快一些：在构造部分子树时，不需要判断 N 次基线条件
此外，这样无须使用 iterator 来跨子程序传递流（扫描）状态
一个坏处是：程序没有那么优雅好看了

接下来讲的实现方式包含三种：

1. 标准方式 — Iterator
a. 把 iterator 的 position 放在递归参数里
b. plain iterator
2. “普通”方式 — 无限 subsequence
我就不写了... 其实很多人这么写的时候也是递归地构造结构，而且对这个问题这么做尤其莫名其妙
3. 优化方式 — foreach 状态机 + 两个显式栈
其中一个栈是用于保存 Heading 深度的，一个栈是保存结果的，只不过碰巧也可以用栈的方式实现

const _1to6 = '1,2,3,4,5,6'.split(',');
function parseHeadingTree(root) {
const isHeading = e => (nm => nm.length > 1 && nm[0] === 'H' && nm[1] in _1to6)(e.tagName);
const headingDepth = e => Number.parseInt(e.tagName[1]); // why not regex?
const peek = (xs) => xs[xs.length -1];
/**/let resultstk = [[]], depthstk = [1]; // 2 stack
for (let elem of root.children) {
if (!isHeading(elem)) continue;
let depth = headingDepth(elem);
let lastdept = peek(depthstk);
if (depth > lastdept) {
depthstk.push(depth);
let subtree = [];
peek(resultstk).push(subtree);
resultstk.push(subtree); }
else if (depth < lastdept) {
depthstk.pop();
resultstk.pop(); }
peek(resultstk).push(elem);
}
return resultstk;
}

发实现走人（慵懒

... 我还打算一遍过的，没想到我对栈组织的还好，对结果的断言没预料到.... 我想想

不过也很快了，程序总共只修改了两次就可以勉强按照预期运行，而且两次
1. 我的一个注释写成了 /*/
2. 我测试的时候给的 document.body 没有 heading

const _1to6 = '1,2,3,4,5,6'.split(',');
const isHeading = e => (nm => nm.length > 1 && nm[0] === 'H' && nm[1] in _1to6)(e.tagName);
const headingDepth = e => Number.parseInt(e.tagName[1]); // why not regex?
const peek = (xs) => xs[xs.length -1];
function parseHeadingTree(root) {
let resultstk = [[]], depthstk = [1];
for (let elem of root.children) {
if (!isHeading(elem)) continue;
let depth = headingDepth(elem);
let lastdept = peek(depthstk), leaf = peek(resultstk);
if (depth > lastdept) {
depthstk.push(depth);
let subtree = [];
leaf.push(subtree);
resultstk.push(subtree); continue; }
else if (depth < lastdept) {
depthstk.pop(); resultstk.pop(); }
leaf.push(elem);
}
return resultstk;
} 争取一下，模拟执行发现一个 bug...
其实我没有主意到 leaf （本身是一个 expression，而不是 value）在过程中发生了更新（if (depth < lastdept) { resultstk.pop(); }）
看来 JS 里没法解决了... 哦不我用箭头函数

至于剩下的问题，就是『栈上重复的引用』
返回前加一个 pop 即可解决

我日，这反 修复失败...

function parseHeadingTree(root) {
const topItem2Stk = (xs) => { let top = xs.pop(); xs.push([top]); };
const deepest = (xs) => { let xx; for (xx = xs; xx.length >0 && xx[0] instanceof Array; xx = xx[0]); return xx; };
let resultstk = [[]], depthstk = [1];
for (let elem of root.children) {
if (!isHeading(elem)) continue;
let depth = headingDepth(elem);
let lastdept = peek(depthstk), leaf = () => peek(resultstk);
if (depth > lastdept) {
depthstk.push(depth);
let subtree = [];
topItem2Stk(resultstk);
leaf().push(subtree);
resultstk.push(subtree); }
else if (depth < lastdept) {
depthstk.pop(); resultstk.pop(); }
leaf().push(elem);
}
let layer = peek(resultstk);
while (layer instanceof Array &&
(layer.length === 0 ||
headingDepth(deepest(layer)) !== 1) ) {
resultstk.pop();
layer = peek(resultstk); } // for top <h1>
return resultstk;
}

为什么一定要 pop 到 <h1>？因为普通情况：

<h1/>
  <h2/>

此时栈顶依然是 h2 的子节点，除非它后面跟了个 h1 使得它被关掉
length == 0 的是不合法的情况，每层至少得有一个 <hn>
len=0 说明它是在读取一个 subtree

沃日，还是不行，策略用错了 这哪里是颗树啊，只有一层...

（拿命继续分析） h4 的时候栈顶为 4
遇到 3 则 depth > lastdept。应该弹出 h4 的栈，所以 h4 实际上没有孙子
h3 遇到 h3 放一起，但我不想这样

我想：h4 遇到 h5 的时候应该接纳 h5... h5 是 h4 的孙子才对
所以就要 deep 放... 得看下一项 是否开启一个 subtree 怎么办呢

const topItem2Stk(xs) => { let top = xs.pop(); xs.push([top]); };
if (depth > lastdept) {
depthstk.push(depth);
let subtree = [];
topItem2Stk(resultstack);
leaf().push(subtree);
resultstk.push(subtree); } 肮脏的做法：若是有的话，我再改回来不就好了！（

const _1to6 = '1,2,3,4,5,6'.split(',');
const isHeading = e => (nm => nm.length > 1 && nm[0] === 'H' && nm[1] in _1to6)(e.tagName);
const headingDepth = e => Number.parseInt(e.tagName[1]); // why not regex?
const peek = (xs) => xs[xs.length -1];
const topItem2Stk = (xs) => { let top = xs.pop(); return (top instanceof Array? top : [top]); };
const deepest = (xs) => { let xx; for (xx = xs; xx.length >0 && xx[0] instanceof Array; xx = xx[0]); return xx; };

function parseHeadingTree(root) {
let resultstk = [[]], depthstk = [1];
function deduceToLevelBase(lev) {
while (peek(depthstk) >= lev) { depthstk.pop(); resultstk.pop(); } }
for (let elem of root.children) {
if (!isHeading(elem)) continue;
let depth = headingDepth(elem);
let lastdept = peek(depthstk), leaf = () => peek(resultstk);
if (depth > lastdept) {
depthstk.push(depth); let parent;
leaf().push(parent = topItem2Stk(leaf()));
let subtree = []; parent.push(subtree);
resultstk.push(subtree); }
else if (depth < lastdept) {
depthstk.pop();
resultstk.pop();
deduceToLevelBase(depth); }
leaf().push(elem);
}
let layer = peek(resultstk);
while (layer instanceof Array &&
(layer.length === 0 ||
headingDepth(deepest(layer)[0]) !== 1) ) {
resultstk.pop();
layer = peek(resultstk); } // for top <h1>
return resultstk;
}

勉强能用的版本，有点小问题

我有点想放弃了，看起来 bug 根本不应该出现

就此算了，可见显式栈的解析器只会更加复杂，难以手写，而不会简单半分
此时已经是凌晨两点了，是我的积累不够而已，就是做不到。 #Algorithm

之前写的那个是堆出来的，我根本就不知道它是基于什么原理....（虽然的确是我自己写的） 输入数据的内涵结构稍微有点变化就会炸，改一点也可能要炸。

虽然我不打算继续了，现在还是说一下这是怎么工作的吧。

上面的 parseHeadingTree 是一个接受 DOM 节点的 ToC （Table of Contents）解析器，它解析目标节点下的所有 h1-h6 heading，来构造一个 header 树

就像这样：

h1
h1
  h2
    h3
  h2
    h5
    h5

[h1
  [h1 [
    [h2 [h3]]
    [h2 [h5 h5]]]]

有两种节点
+ 当前层节点 <h1-h6>
+ 子树节点 [<h1-h6> [...]]

它的解析规则很简单
a. 有一个栈用于记录当前嵌套 heading 的层次, 初始化为 [1]
b. 有一个栈用于放置 <h1-h6> 的嵌套解析状态, 初始化为 [ [] ]
+ 每次要添加元素的时候，都加到 peek(resultstk) 里，因为它代表当前层正在架构的数据对象
e.g.

h1 [[h1]]
h1 [[h1 h1]]
  h2 [a [h1 [h1 a=[h2]]]] 

然后，如果遇到一个 h1 (h1 < h2) 就停止构建 <h2> 的 children，然后把 h1 加到当前层上
h1

[[h1 [h1 a=[h2]] h1]]

这个结论对所有『递归』层都是有效的，也就是说这里的 h2 后面再跟 h3 h4 都是一样的
否则，如果它是最后一个呢？在 for 后面有个 while 就是解决这个问题的，它把所有正在读取还未结束的层给 pop 掉，保证结果单一

+ 如果当前深度增加了，则将上一个标签转换为 stack，加入自己这一层并且进入

  let parent;
      leaf().push(parent = topItem2Stk(leaf()));
      let subtree = []; parent.push(subtree);

resultstk.push(subtree); 当然它还不够健壮，因为如果第一个就是 <h2> 而不是 h1 的话，topItem 就不存在了... 我写个特殊标签吧
+ 如果当前深度不变，什么都不做
+ 如果当前深度减小了，弹出当前深度、弹出一次结果栈（当前构造）
你也可以理解为给构造动态加 ] 闭括号，就是通过弹出栈的方式
最后，把标签送进当前构造的子树里面去，这就实现了无限深度的铺平构造
可是还有一片小乌云。

比方说

h1
  h2
      h5
    h4

我们一般认为 h5 h4 都是 h2 的元素，可是因为上面规则的幼稚性， h5 是 h2 的元素，h4 却不是（h4.depth < h5.depth）
准确的说，一般递归扫描的时候也是『遇到第一个 depth > currentdept 的时候停下』，可我们的这个 context 是基于显式栈的
我想到的方法是（也是递归的时候栈的一种情况）每次 (h4.depth < h5.depth) 的时候，不断 deduce 栈，直到 (h4.depth >= layer.depth) （找到第一个基层）

h1 [h1
  h2 [h1 [h2
      h5 [h1 [h2 [h5
    h4

a. ]](关闭的是 h2 的栈... 不是 h5 的)
b. {- 找到第一个开括号 [h2 -}
] [h4]]

我也是才知道，其实我之前写的也没解决这个问题.... 看起来倒是进步了

有点小瑕疵（因为脑力不够...） 不过还能用（因为存在 [[...] ...] 和 [a ...] 的区别） 😂 算是完成 不过正式使用还是递归下降法的...

#HTML #JS #FP #Algorithm

也是瞎堆的，因为这真是很麻烦... 处理起来 意外很多，本身数据结构设计的就比较 懒惰(laziness)

#JavaScript #web 恭喜 duangsuse 成功获得：『面向排错编程』『面向 REPL 编程』『数学的智障』称号！ 以上弱智的代码，居然全是我在 REPL 里试过三次以上才改出来的，我现在心里非常难受