简单的面试题之目录树构建

01_main.ts

/**
 * 给一个字符串(是一段markdown文本)，根据这个字符串生成出这段文本的目录结构
 */

/**
 * 输入
 */
const input = `# Title h1
hsh
## Title h2 sibling
tatat
### Title h3
test
#### Title h4
## Title h2
`;

/**
 * 实现transform函数，并且完善ContentNode类型
 */

interface ContentNode {}

function transform(md: string): ContentNode[] {
  return [];
}

console.log(JSON.stringify(transform(input), undefined, 2));

// 预期输出：
const output: ContentNode[] = [
  {
    text: "Title h1",
    type: "h1",
    children: [
      {
        text: "Title h2 sibling",
        type: "h2",
        children: [
          {
            text: "Title h3",
            type: "h3",
            children: [
              {
                text: "Title h4",
                type: "h4",
                children: [],
              },
            ],
          },
        ],
      },
      {
        text: "Title h2",
        type: "h2",
        children: [],
      },
    ],
  },
];

02_answer.ts

const input = `# Title h1
hsh
## Title h2 sibling
tatat
### Title h3
test
#### Title h4
## Title h2
`;

interface ContentNode {
  text: string;
  type: string;
  children: ContentNode[];
}

function transform(md: string): ContentNode[] {
  const parseLine = (
    line: string
  ): { text: string; level: number } | undefined => {
    let level = 0;
    for (let i = 0; i < line.length; ++i) {
      if (line[i] === "#") {
        level++;
      } else {
        break;
      }
    }
    if (level) {
      return {
        text: line.slice(level + 1),
        level,
      };
    }
    return undefined;
  };
  const stack: ContentNode[] = [
    {
      type: `h0`,
      text: "",
      children: [],
    },
  ];
  for (const line of md.split("\n")) {
    const res = parseLine(line);
    if (res) {
      const { text, level } = res;
      const hxStr = `h${level}`;
      while (stack.length > 1 && stack[stack.length - 1].type >= hxStr) {
        stack.pop();
      }
      const node = {
        text,
        type: hxStr,
        children: [],
      };
      stack[stack.length - 1].children.push(node);
      stack.push(node);
    }
  }
  return stack[0].children;
}

console.log(JSON.stringify(transform(input), undefined, 2));

const output: ContentNode[] = [
  {
    text: "Title h1",
    type: "h1",
    children: [
      {
        text: "Title h2 sibling",
        type: "h2",
        children: [
          {
            text: "Title h3",
            type: "h3",
            children: [
              {
                text: "Title h4",
                type: "h4",
                children: [],
              },
            ],
          },
        ],
      },
      {
        text: "Title h2",
        type: "h2",
        children: [],
      },
    ],
  },
];

console.assert(
  JSON.stringify(transform(input), undefined, 2) ===
    JSON.stringify(output, undefined, 2)
);