记一道算法题解题思路，字符串解析成标题结构

这是我参与更文挑战的第4天，活动详情查看： 更文挑战

写作背景

那是一个月黑风高，伸手不见五指的（并不是因为我黑）的夜晚，我的小伙伴给我发了一道算法题，题目如下。

将题中的字符串text解析为一个标题树。

const text = `
- 章节一
  - 标题一
  - 标题二
    - 小节四
- 章节二
  - 标题一
  - 标题二
  - 标题三
    - 子标题四
      - 小节五
`;
class Node {
  constructor({ value, level }) {
    this.value = value;
    this.level = level;
    this.children = [];
    // hint: 也可在数据结构中增加 this.parent 节点辅助解析
  }
}

const tree = parseTree(text);
// [
//   Node { value: "章节一", children: [ Node, Node ], level: 1 },
//   Node { value: "章节二", children: [ Node, Node ], level: 1 } 
// ]

function parseTree(text){
    // code
}
复制代码

在细细思索之后，砸吧砸吧嘴，这会不会我小伙伴钓鱼，他自己写不出来所以让我来帮他写？

这玩意和掘金的文章阅读页里，右侧的目录不能说是很像，只能说是一模一样。

虽然有段时间没摸算法了，但是我凭直觉认为，这道题，我ok的。

准备工作

准备工作其实没啥，先创建好一个html文件，然后把上面的基础代码复制过来，然后在浏览器打开下。

然后走到厨房，拿起左手第三个罐子，从里面掏出一包黑色的，新到的茶包，泡一杯热茶，反正接下来一段时间也睡不着， 那就让自己更清醒点。

嘻嘻嘻，皮一下，该有的准备工作还是要的， 我这该死的仪式感。

实现思路

最简单的实现思路很简单，就是肉眼可见的两个空格为一个level， 即没有双空格前缀是level 1，一个双空格，就是level 2， 以此类推。

version 1.0

function parseTree(text){
    let parent = new Node({value: '', level: 0}); // 创建一个根节点，方便更新父节点
    let level = 1; // 用于后续标题的层级递进
    let flag = '  '; // 层级标识，默认是两个空格
    
    for(let item of text.split('\n')){ // 先将字符串按换行切割，用于遍历
        if(!item) continue // 如果当前项为空，直接跳过
        // 递归确定当前项具体在第几层
        // 每次递归处理的都是确认当前项的层级，
        // 所以不用当心断层会识别不了情况。
        checkFlag(item, level, parent, flag)
    }
    
    /**
     * @params item 当前需要处理的项
     * @params level 当前项的默认level
     * @params parent 当前项的父节点
     * @params flag 用于计算当前项的level
    */
    function checkFlag(item, level, parent, falg){
        if(item.indexOf(flag) !== -1){ // 如果当前项存在双空格前缀，标识不是当前level
            let len = parent.children.length;
             //重新确认父级 如果当前父级存在子节点，那么将自己设为新父级
            parent = len ? parent.children[length - 1] : parent;
            // 这里注意，不管是否更新父级，当前层级需要level + 1
            checkFlag(item.substr(flag.length, item.length), level + 1， parent, flag)
        } else {
            // 这里的item.substr是为了祛除字符串中的'- '前缀
            parent.children.push(new Node({value: item.subnstr(2, item.length), level: level}))
        }
    }
    
    return parent.children;
}
复制代码

具体实现

其实这里对当时的场景做了下PS， 我并没有直接去思考固定标志为双空格的情况，因为考虑到前缀是有可能变化的，我想一步到位，写一个能自动识别标题前缀的，所以当时着实纠结了一番。

还和朋友吵了一段时间， 他想让我直接按双空格我实现，我偏不， 我觉得那样太简单了，我想加个level， 以下是我直接实现的，逻辑部分和上面的代码一致，只是加了识别前缀的部分。

首先，第一步，改造默认的标题字符串

这里假设应用于掘金的文章Markdown解析，显不出力内容节点，只看标题节点，大致如下

const text = `
#- 章节一
##- 标题一
##- 标题二
###- 小节四
#- 章节二
##- 标题一
##- 标题二
##- 标题三
###- 子标题四
####- 小节五
`;
复制代码

那么这时候他的标题标识符就变了，当然在上面的代码里，修改flag的默认值就能解决了，但是这不是我想要的。

我想让他自己识别，所以我希望在他碰到第一个标题时，去自动获取标题的标识符。

function parseTree(text){
    let parent = new Node({value: '', level: 0}); // 创建一个根节点，方便更新父节点
    let level = 1; // 用于后续标题的层级递进
    let flag = null; // 层级标识，默认为空
    
    for(let item of text.split('\n')){ // 先将字符串按换行切割，用于遍历
        if(!item) continue // 如果当前项为空，直接跳过
        
        // 遇到首个非一级标题时，确认段落标识
        if(!flag && item.indexOf('- ') !== 0){
            flag = item.substr(0, item.indexOf('- '))
        }
        
        // 调用递归用于确认层级
        checkFlag(item, level, parent, flag)
    }
    
    /**
     * @params item 当前需要处理的项
     * @params level 当前项的默认level
     * @params parent 当前项的父节点
     * @params flag 用于计算当前项的level
    */
    function checkFlag(item, level, parent, falg){
        if(item.indexOf(flag) !== -1){ // 如果当前项存在双空格前缀，标识不是当前level
            let len = parent.children.length;
             //重新确认父级 如果当前父级存在子节点，那么将自己设为新父级
            parent = len ? parent.children[length - 1] : parent;
            // 这里注意，不管是否更新父级，当前层级需要level + 1
            checkFlag(item.substr(flag.length, item.length), level + 1， parent, flag)
        } else {
            // 这里的item.substr是为了祛除字符串中的'- '前缀
            parent.children.push(new Node({value: item.subnstr(2, item.length), level: level}))
        }
    }
    
    return parent.children;
}
复制代码