如何修复此算法以在 AST 中创建嵌套部分

Question

我正在努力创建一个算法，该算法采用兄弟元素数组（DOM 节点的抽象表示）和 returns 该数组通过嵌套增强。嵌套规则非常简单：每个标题都开始一个新部分，该部分跨越同一级别（或列表末尾）的下一个标题。每个部分都可以有更多的嵌套部分，规则相同。

背景：我正在尝试将我的 CMS 中的 AST 转换为 Chris Coyers post about the interactive sticky table of contents. Currently, i am using only headings to create a similar effect, (e.g. scotch.io 中显示的结构，但效果并不那么流畅。

我能够创建一些嵌套，但我的大脑不太喜欢这样的递归算法，而且我遇到了至少一个错误——嵌套的一部分被不需要的数组填充（注意第一个“heading3”等等）。

到目前为止我得到了什么：

let list = ["heading1", "1", "1", "heading2", "1-1", "1-1", "heading3", "1-1-1", "heading3", "1-1-2", "1-1-2", "heading2", "1-2", "1-2", "heading1", "heading2", "2-1", "heading2", "2-2", "heading1", "3", "heading1", "4", "4", "4"]

let findFirstHeading = (list, level) => list.findIndex(el => new RegExp(`heading${level}`).test(el))

let splitIntoSections = (list, level) => {
  let startIndex = findFirstHeading(list, level)
  // Note: while this might seem overcomplicated, it is due to prevent bug, when findIndex returns -1, then adding startIndex + 1 will give a faulty value.
  let endIndex =
    findFirstHeading(list.slice(startIndex + 1), level) === -1 ?
    -1 :
    findFirstHeading(list.slice(startIndex + 1), level) + startIndex + 1
        
  let precedingList = list.slice(0, startIndex)
  let restOfList = endIndex > -1 ? list.slice(endIndex) : null

  return restOfList ? [...precedingList,
    splitIntoSections(list.slice(startIndex, endIndex), level + 1),
    ...splitIntoSections(restOfList, level)
  ] : [list]
}

console.log(JSON.stringify(splitIntoSections(list, 1), null, 2))

预期结果：

[
  [
    "heading1",
    "1",
    "1",
    [
      "heading2",
      "1-1",
      "1-1",
      [
        "heading3",
        "1-1-1"
      ],
      [
        "heading3",
        "1-1-2",
        "1-1-2"
      ]
    ],
    [
      "heading2",
      "1-2",
      "1-2"
    ]
  ],
  [
    "heading1",
    [
      "heading2",
      "2-1"
    ],
    [
      "heading2",
      "2-2"
    ]
  ],
  [
    "heading1",
    "3"
  ],
  [
    "heading1",
    "4",
    "4",
    "4"
  ]
]

如有任何帮助，我们将不胜感激。谢谢。

Answer 1

通常在编写递归算法时，我会避免源数组的副本或子副本，而是选择一个索引来跟踪源数组中的当前位置，主要是为了避免数组复制对性能的影响。通常我发现让主函数需要最少的参数是一个更清晰的函数接口，并将实际的递归函数以及递归函数所需的任何变量的初始化嵌入到这个主函数中。

我在下面的代码中嵌入了一些注释，以帮助理解递归逻辑。

function nest( array ) {
  
  function recurse( currentLevel ) {
    let result = [];
    while ( index < array.length ) {
      let value = array[ index ];
      if ( value.slice( 0, 7 ) == 'heading' ) {
        let newLevel = +value.slice( 7 );
        if ( currentLevel < newLevel ) {
          // If the new heading is deeper than the current heading, then push
          // the heading value as a new child array to the result, and recursively
          // continue adding to this new child array.
          index++;    // Advance past the 'headingX' as it's added to the child array.
          result.push( [ value, ...recurse( newLevel ) ] );
        } else {
          // Otherwise, if the new heading is less than or equal, then close out
          // the current array, adding it to parent array.  And don't advance past
          // this 'headingX' as the parent recurse function will pick it up.
          return result;
        }
      } else {
        // Otherwise, if not 'headingX' simply add the value to the result.
        result.push( value );
        index++;
      }
    }
    return result;
  }
  
  let index = 0;
  return recurse( 0 );
}
  
  
let list = ["heading1", "1", "1", "heading2", "1-1", "1-1", "heading3", "1-1-1", "heading3", "1-1-2", "1-1-2", "heading2", "1-2", "1-2", "heading1", "heading2", "2-1", "heading2", "2-2", "heading1", "3", "heading1", "4", "4", "4"];

console.log( nest( list ) );

Answer 2

虽然我肯定会接受@Trentium 提供的答案，但同时我能够自己发现代码中的错误：

有一种情况我没有想到：在列表的切片中找不到标题。在那种情况下，我应该 return list 而不是 [list] （因此嵌套的额外级别）。

let list = ["heading1", "1", "1", "heading2", "1-1", "1-1", "heading3", "1-1-1", "heading3", "1-1-2", "1-1-2", "heading2", "1-2", "1-2", "heading1", "heading2", "2-1", "heading2", "2-2", "heading1", "3", "heading1", "4", "4", "4"]

let findFirstHeading = (list, level) => list.findIndex(el => new RegExp(`heading${level}`).test(el))

let splitIntoSections = (list, level) => {
  let startIndex = findFirstHeading(list, level)

  if (startIndex === -1) { // <-- If no more heading is found, return list, not [list]
    return list
  } else {

    // Note: while this might seem overcomplicated, it is due to prevent bug, when findIndex returns -1, then adding startIndex + 1 will give a faulty value.
    let endIndex =
      findFirstHeading(list.slice(startIndex + 1), level) === -1 ?
      -1 :
      findFirstHeading(list.slice(startIndex + 1), level) + startIndex + 1

    let precedingList = list.slice(0, startIndex)
    let restOfList = endIndex > -1 ? list.slice(endIndex) : null

    return restOfList ? [...precedingList,
      splitIntoSections(list.slice(startIndex, endIndex), level + 1),
      ...splitIntoSections(restOfList, level)
    ] : [list]
  }
}

console.log(JSON.stringify(splitIntoSections(list, 1), null, 2))

如何修复此算法以在 AST 中创建嵌套部分

How to fix this algorithm to for create nested sections in an AST

javascript

algorithm

recursion

abstract-syntax-tree