javascript - 如何使用非递归算法生成 XML(结束标记部分有问题)

Question

使用递归生成 XML 非常容易。

function xml(node) {
  var str = []
  str.push('<' + node.tag + '>')
  node.children.forEach(function(child){
    str.push(xml(child))
  })
  return str.join('')
}

但我很难弄清楚如何在不递归的情况下完成同样的事情。

写一个非递归循环很容易:

function loopWithoutRecursion(node, fn) {
  var stack = [node]
  while (stack.length) {
    var node = stack.pop()
    fn(node)
    if (node.children) {
      node.children.forEach(function(child){
        stack.push(child)
      })
    }
  }
}

像这样使用:

loopWithoutRecursion(start, function(node){
  // ...
})

但棘手的部分是如何处理结束标签:

var str = []
loopWithoutRecursion(node, function(node){
  str.push('<' + node.tag + '>')
  // ... I'm stuck
})

我试过这种方法，但没有用:

var openStr = []
var closeStr = []
loopWithoutRecursion(node, function(node){
  openStr.push('<' + node.tag + '>')
  closeStr.push('</' + node.tag + '>')
})

var str = []
openStr.forEach(function(openTag, i){
  var closeTag = closeStr[i]
  str.push(openTag + closeTag)
})

但这和这样做是一样的:

var str = []
loopWithoutRecursion(node, function(node){
  str.push('<' + node.tag + '>')
  str.push('</' + node.tag + '>')
})

所以我想知道这个问题是否有直接的解决方案，或者是否需要跳过很多环节(创建很多中间结构)。我觉得计算机科学可能已经很容易解决了这个问题，但我不知道从哪里开始。

Answer 1

有一个相当简单的解决方案。每次进行递归调用时，它实际上都被推送到所谓的调用堆栈 ( https://en.wikipedia.org/wiki/Call_stack )。调用堆栈的基本内容是它(大致)包含调用函数时使用的参数，以及一个返回指针 - 代码中应该在函数完成后执行的位置。我真的建议阅读更多有关如何在引擎盖下调用函数的信息，这将清除很多内容。

通常，您的堆栈需要包含参数 和要执行的操作。

解决方案

简化伪代码中的递归函数:

func xml(node):
    print node.open_tag
    for child in node.children:
        xml(child)
    print node.close_tag

在这种情况下，参数部分很简单 - 它只是节点。但是，要做的事情可能会有所不同。

• 如果您刚刚开始处理标签，您应该打印开头，然后开始处理子项。
• 如果您要从 child 返回给 parent ，您应该关闭标签。

这正是我在这里所做的:

function loopWithoutRecursion(node, open, close) {
  var stack = [[node, 'open']]
  while (stack.length) {
    var stack_frame = stack.pop()
    var node = stack_frame[0]
    var mode = stack_frame[1]

    if (mode == 'open') {
      open(node)

      stack.push([node, 'close'])

      if (node.children) {
          node.children.reverse().forEach(function(child){
            stack.push([child, 'open'])
          })
      }
    } else {
      close(node)
    }
  }
}