This is the fourth day of my participation in Gwen Challenge

Writing background

It was a dark and windy night (not because I was dark), and my little friend sent me an algorithm problem. The topic was as follows.

Parse the string text in the problem into a title tree.

const text = '- Section 1 - Heading 1 - Heading 2 - Subsection 4 - Section 2 - Heading 1 - Heading 2 - Heading 3 - Sub-heading 4 - Subsection 5';
class Node {
  constructor({ value, level }) {
    this.value = value;
    this.level = level;
    this.children = [];
    // hint: You can also add this. Parent node to the data structure to aid parsing}}const tree = parseTree(text);
/ / /
// Node {value: "section 1 ", children: [Node, Node], level: 1},
// Node {value: "分 二", children: [Node, Node], level: 1}
// ]

function parseTree(text){
    // code
}
Copy the code

After careful consideration, smash it, smash it, is it possible that my friend fishing, he can not write himself, so let me help him write?

This is not exactly the same as the table of contents on the right side of the reading page of the gold digger articles.

I haven’t touched the algorithm in a while, but MY intuition tells me that I’m ok with this one.

The preparatory work

The preparation work is not much, first create an HTML file, then copy the above basic code, and open it in the browser.

Then walk to the kitchen, pick up the third jar on your left hand, take out a black, freshly arrived teabag, and make a hot cup of tea. You won’t be able to sleep for a while anyway, so you’ll feel more awake.

Hee hee hee, skin, the preparation is still necessary, my damn sense of ritual.

Implementation approach

The simplest implementation idea is that two visible Spaces are a level, that is, no double space prefix is level 1, a double space is level 2, and so on.

Version 1.0

function parseTree(text){
    let parent = new Node({value: ' '.level: 0}); // Create a root node to update the parent node
    let level = 1; // For subsequent title progression
    let flag = ' '; // Hierarchy identifier. Default is two Spaces
    
    for(let item of text.split('\n')) {// Cut the string into newlines for traversal
        if(! item)continue // If the current entry is empty, skip it
        // Determine the level of the current item recursively
        // Each recursion verifies the current item's level,
        // So don't be afraid that the fault will not recognize the situation.
        checkFlag(item, level, parent, flag)
    }
    
    / * * *@params Item Current item to be processed *@params Level Indicates the default level * of the current item@params Parent Parent of the current item *@params Flag Calculates the level */ of the current entry
    function checkFlag(item, level, parent, falg){
        if(item.indexOf(flag) ! = = -1) {// If the current entry has a double space prefix, it is not the current level
            let len = parent.children.length;
             If the current parent has child nodes, set yourself as the new parent
            parent = len ? parent.children[length - 1] : parent;
            // Note that the current level requires level + 1 regardless of whether the parent level is updated
            checkFlag(item.substr(flag.length, item.length), level + 1, the parent, flag)}else {
            // Item. substr is used to remove the '- 'prefix from the string
            parent.children.push(new Node({value: item.subnstr(2, item.length), level: level}))
        }
    }
    
    return parent.children;
}
Copy the code

The specific implementation

In fact, I did some PHOTOSHOP for the scene at that time. I didn’t directly think about the situation where the fixed logo was double space, because considering that the prefix may change, I wanted to write a title prefix that can automatically recognize, so I was really confused.

I also argued with my friend for some time, he wanted me to directly press double space to achieve my implementation, BUT I did not, I think that is too simple, I want to add a level, the following is my direct implementation, the logic part is consistent with the above code, but added the recognition prefix part.

First, modify the default title string

Here, it is assumed that the article Markdown analysis applied to digging gold does not show the content node and only looks at the title node, which is roughly as follows

const text = ` a # # # - section - headlines 2 # # # - # # # - section 4 - chapter 2 a # # # # - captions - headlines three # # # # # 2 - - subtitle 4 # # # # - section 5 `;
Copy the code

In this case, the title identifier is changed. Of course, in the above code, changing the default value of flag can solve the problem, but this is not what I want.

I want him to identify himself, so I want him to automatically get the identifier for the title when he hits the first one.


function parseTree(text){
    let parent = new Node({value: ' '.level: 0}); // Create a root node to update the parent node
    let level = 1; // For subsequent title progression
    let flag = null; // Hierarchy identifier, empty by default
    
    for(let item of text.split('\n')) {// Cut the string into newlines for traversal
        if(! item)continue // If the current entry is empty, skip it
        
        // When the first non-level heading is encountered, verify the paragraph identifier
        if(! flag && item.indexOf(The '-')! = =0){
            flag = item.substr(0, item.indexOf(The '-'))}// Call recursion is used to validate the hierarchy
        checkFlag(item, level, parent, flag)
    }
    
    / * * *@params Item Current item to be processed *@params Level Indicates the default level * of the current item@params Parent Parent of the current item *@params Flag Calculates the level */ of the current entry
    function checkFlag(item, level, parent, falg){
        if(item.indexOf(flag) ! = = -1) {// If the current entry has a double space prefix, it is not the current level
            let len = parent.children.length;
             If the current parent has child nodes, set yourself as the new parent
            parent = len ? parent.children[length - 1] : parent;
            // Note that the current level requires level + 1 regardless of whether the parent level is updated
            checkFlag(item.substr(flag.length, item.length), level + 1, the parent, flag)}else {
            // Item. substr is used to remove the '- 'prefix from the string
            parent.children.push(new Node({value: item.subnstr(2, item.length), level: level}))
        }
    }
    
    return parent.children;
}
Copy the code