递归大法好,30 行代码为 Markdown 生成目录树

2018/1/22 posted in  技术分享

目录

前言

本以为我的博客程序是没有 [TOC] 这样东西来自动生成目录树的,都已经把代码写好了,一看文档就懵逼了。原来文档最后一条写明了,[TOC] 以及其用法,是我自己没好好看文档,心痛。

不过既然写完了,那就把原理分享出来吧,反正也就 30 行代码。千万别钻牛角尖跟我说超过了 30 行,你硬是觉得括号占一行也算行的话我也没办法。

第一步、提取标题

既然要为 Markdown 生成目录树,那么第一个步骤就是提取 Markdown 中的所有标题。因为 Markdown 本身语法非常简单,由若各个 # 符号开头,所以可以用一个正则表达式 /^(#+)[ \t](.*)$/ 进行匹配提取。(#+) 用来提取是第几级的标题,(.*) 用来提取出具体标题内容。因为很多 Markdown 实现里面都要求标题的 # 符号后面要跟空格或者 tab 来进行分隔,所以我们也按照这样的标准,用 [ \t]+ 来强制要求至少有一个空格或者 tab 进行分隔。

下面这个 getHeaders 就是用来提取一个 Markdown 里面标题的,具体过程如下:

  1. 将 Markdown 文件用 split('\n') 分成一个行数组。
  2. 将行数组里面的每一行用 /^(#+)[ \t](.*)$/ 进行匹配和提取标题。
  3. 过滤掉不匹配的行。
  4. 最后将提取出来的字符整理成一个级数和标题的对象。
const getHeaders = text =>
    text
        .split('\n')
        .map(line => line.match(/^(#+)[ \t]+(.*)$/))
        .filter(header => header !== null)
        .map(([, prefix, title]) => ({ level: prefix.length, title }))

getHeaders 函数会提取出一个 Markdown 文件里面所有的标题信息,这个标题信息里面包含了标题的级数和标题内容。

第二步、生成目录树

经过第一步提取过,我们就得到了一个标题列表,但是光有标题列表是不行的,我们希望得到的是一个目录树。直射后我们就需要把一个铺平的标题列表折叠成一个目录树。不过这样要怎么做呢?

大家都听过或者玩过“汉诺塔”这个游戏吧?大家在刚学习编程的时候,当老师或者书本讲到“递归”这个概念的时候,往往都会以汉诺塔这个游戏作为例子。我们人在解汉诺塔这个问题的时候还是挺复杂的,但是对于计算机来说,解决汗汉诺塔问题只需要三步。

   #
  ###
 #####
#######
-------   -------   -------

第一步:

             #
            ###
#######    #####
-------   -------   -------
  
第二步:

             #
            ###
           #####    #######
-------   -------   -------

第三步:
                       #
                      ###
                     #####
                    #######
-------   -------   -------

玩过汉诺塔的小伙伴一定会想说:“麻麻!它犯规!”。但其实计算机里面解汉诺塔就是那么简单的步骤,这里面涉及到一个是“递归”的思想,另一个其实非常著名也是非常常用到算法设计思想——分治。分治分治,就是分而治之的意思,将一个复杂的问题不断分解成多个简单的小问题的一种思想。如果你把顶上三个当成一块,然后递归对上面的块运用相同的算法,最后就能得到我们想要的结果了。

现在回到我们生成目录树的例子来,同样,甚至比汉诺塔更简单,只需要两步。

  1. 获取第一个标题,令为 parent。
  2. 从 parent 节点后一个节点开始,将连续比 parent 节点层级低的节点组成的列表令为 children。
  3. 对 children 重复本算法,并赋值给 parent.children 属性。
  4. 对剩余的节点组成的列表重复本算法。
以下是一个标题列表
[
    # header1,
    ## header2,
    ### header3,

    # header1,
    ## header2,
    ### header3
]

第一步:获取第一个标题,令为 parent。

parent = # header1

[
    # header1, <- parent
    ## header2,
    ### header3,

    # header1,
    ## header2,
    ### header3
]

第二步:从 parent 节点后一个节点开始,将连续比 parent 节点层级低的节点组成的列表令为 children。

parent = # header1
children = [
    ## header2,
    ### header3
]

[
    # header1, <- parent
    ## header2, <- children
    ### header3, <- children

    # header1,
    ## header2,
    ### header3
]

第三步:对 children 重复本算法,并赋值给 parent.children 属性。

parent = # header1
children = [
    ## header2,
    ### header3
]
parent.children = 重复本算法(children)

[
    # header1, <- parent
    ## header2, <- children
    ### header3, <- children

    # header1,
    ## header2,
    ### header3
]

第四步:对剩余的节点组成的列表重复本算法。

parent = # header1
children = [
    ## header2,
    ### header3
]
parent.children = 重复本算法(children)
剩余节点列表 = [
    # header1,
    ## header2,
    ### header3
]
重复本算法(剩余节点列表)

[
    # header1, <- parent
    ## header2, <- children
    ### header3, <- children

    # header1, <- 剩余节点
    ## header2, <- 剩余节点
    ### header3 <- 剩余节点
]

代码如下:

// result 用来缓存中间结果。
const createIndex = (headers, result = []) => {
    if (headers.length == 0) return result // 如果标题列表为空(已经把标题列表便利完了),则返回缓存的结果。
    
    // 第一步
    const parent = headers[0];
    
    // 第二步
    const children = headers.slice(
        1,
        headers
            .slice(1)
            .findIndex(header => header.level <= parent.level) + 1 || headers.length
    )
    
    // 第三步
    parent.children = createIndex(children);
    
    // 第四步
    return createIndex(
        headers.slice(children.length + 1),
        result.concat([parent])
    )
}

第三步、生成 Markdown 语法的嵌套结构目录树

在上一步中,我们已经得到了一个有层级关系树状结构的目录输了,这一部分相当于根据层级打印这个目录树。同样的,我们只需要打印一级,然后再通过递归的方式将答应函数运用到子树上就行了。经过上一个步骤的洗礼,我相信小伙伴理解这一步一定非常简单。

const renderIndex = (index, numbered = false, indent = 4, indent_char = ' ') =>
    index
        .map(({ level, title, children }, i) => 
            indent_char.repeat((level - 1) * indent)
                + (numbered ? (i + 1) + '. ' : '* ')
                + `[${title}](#${title})`
                + (children.length > 0 ?  '\n' + renderIndex(children, numbered, indent, indent_char) : '')
        )
        .join('\n')

其他骚操作

既然小伙伴们都看到这里了,那么聪明的你有没又发现你被坑了?如果没发现的话,请看下面一段代码。

const renderHeaders = (headers, numbered = false, indent = 4, indent_char = ' ') =>
    headers
        .map(({ level, title }) =>
            indent_char.repeat((level - 1) * indent)
            + (numbered ? (i + 1) + '. ' : '* ')
            + `[${title}](#${title})`)
        .join('\n')

发现了没有,其实可以完全跳过第二步,直接打印出来的,哈哈哈哈。我只是单纯想拿这个例子讲递归而已啦,所以才会饶了那么打一个圈。

上面讲了那么多递归,现在其实可以讲一讲非递归的实现方式。其实任何递归都可以用循环+栈进行替代,只不过相比递归的方式来说要复杂繁琐得多。递归在多数情况下都更接近数学上的美感。当然在这个例子中,循环+栈在处理一些非常深层级的大文件上面具有更好的性能。

const createIndexByStack = _headers => {
    // 预处理,并添加终止符, 用终止符强迫所有 header 出栈
    const headers = _headers.concat([{level: 1}]).map(header => {
        header.children = [];
        return header;
    })

    const stack = []

    // 构造 top 方法,方便获取栈顶
    stack.top = () => stack[stack.length - 1] || null 

    // 在栈低压入根节点
    stack.push({ level: 0, children: [] })

    for (const header of headers) {
        while (header.level <= stack.top().level) {
            const child = stack.pop()
            stack.top().children.push(child)
        }
        stack.push(header)
    }

    // 弹出终止符
    stack.pop() 

    // 弹出根节点结果
    return stack.pop().children
}

递归多是用自顶向下的分析方式,表达方式更形而上,更方便人的理解。而用循环+栈多是自底向上的分析方式,更繁琐而复杂,但是对计算机友好,往往也有更好的性能。

后语

为了跟前言能够首尾呼应,我在这里写多一个后语。这是新博客第一篇技术分享类的文章,虽然讲的内容非常的简单,但是我个人还是非常满意的,我个人觉得核心的思想和细节都已经讲到为了,并且也提供了具体的代码实现,对没有什么耐心的我来说也是一种挑战吧。

附:完整代码

const getHeaders = text =>
    text
        .split('\n')
        .map(line => line.match(/^(#+)[ \t]+(.*)$/))
        .filter(header => header !== null)
        .map(([, prefix, title]) => ({ level: prefix.length, title }))

const createIndex = (headers, result = []) => {
    if (headers.length == 0) return result
    const parent = headers[0];
    const children = headers.slice(
        1,
        headers
            .slice(1)
            .findIndex(header => header.level <= parent.level) + 1 || headers.length
    )
    parent.children = createIndex(children);
    return createIndex(
        headers.slice(children.length + 1),
        result.concat([parent])
    )
}

const renderIndex = (index, numbered = false, indent = 4, indent_char = ' ') =>
    index
        .map(({ level, title, children }, i) => 
            indent_char.repeat((level - 1) * indent)
                + (numbered ? (i + 1) + '. ' : '* ')
                + `[${title}](#${title})`
                + (children.length > 0 ?  '\n' + renderIndex(children, numbered, indent, indent_char) : '')
        )
        .join('\n')

// ================ 测试 ==============
const text = `
# header1
## header2
### header3
# header1
## header2
### header3
`

console.log('========== text ===========\n', text)
const headers = getHeaders(text)
console.log('========== headers ===========\n', headers)
const index = createIndex(headers)
console.log('========== index ===========\n', index)
const markdown = renderIndex(index)
console.log('========== markdown ===========\n', markdown)