使用JavaScript从平面数组生成树形结构（不使用对象引用）

Question

我试图从一个平面数组中生成JavaScript树形结构。这通常是一个相当简单的命题 - 只需保留一个“堆栈”数组，其中包含按嵌套深度排序的当前工作范围祖先对象的引用，当进入另一个嵌套级别时将一个新元素推送到堆栈上，并在离开一个级别时将其弹出，用新的最后一个数组项引用的对象替换当前的工作元素。

不幸的是，这需要传递引用的能力，而JavaScript没有（好吧，没有以我知道如何在此问题上使用的任何有意义的方式）。

为了背景介绍一下，我正在尝试将一个任意长/复杂的字符串转换为类似于下面的结构的嵌套XML风格（但不是 XML，因此不能使用XML解析器）令牌： 预期输入：

[
    "<token>",
    "<my non compliant token>",
    "some text at this level",
    "<some other token>",
    "some more text",
    "<yet another token>",
    "more text",
    "</yet another token>",
    "blah!",
    "</some other token>",
    "</token>",
    "more text"
]

期望输出

[
    {
        "token": "<token>",
        "children": [
            {
                "token": "<my non compliant token>",
                "children": [
                    "some text at this level",
                    {
                        "token": "<some other token>",
                        "children": [
                            "some more text",
                            {
                                "token": "<yet another token>",
                                "children": [ "more text" ]
                            },
                            "blah!"
                        ]
                    }
                ]
            }
        ]
    },
    "more text"
]

为了澄清，我不需要整个算法（但如果您愿意提供您的实现，我会很感兴趣） - 我只需要一种在输出树中维护当前位置的好方法（或者是生成树对象的完全不同/更好的方式！）不要太关注令牌的工作方式 - 它们不是XML，并且对于这个练习的目的可以完全以不同的形式格式化。非常感谢任何输入！

- Christopher

Answer 1

您的字符串看起来很容易解析。我认为我会这样做：

var stack = [];
var array = [];
for (var i in strings) {
   var s = strings[i];
   if (s.indexOf("</") == 0) {
      array = stack.pop();
   } else if (s.indexOf("<") == 0) {
      var obj = {token: s, children: []};
      array.push(obj);
      stack.push(array);
      array = obj.children;
   } else {
      array.push(s);
   }
}

- Maurice Perry

---

谢谢。由于使用了对象属性，它允许一种伪传引用的方式，这对我很有效！ - Christopher

Answer 2

想法 #1

这是一个你可能没有预料到的答案。

看着你期望的输出，我在想是否最简单的方法就是生成 JSON，然后在完成后进行 eval。完全没有引用。

当遍历你的扁平数组时，你基本上有三个操作：

1. 向当前对象添加更多数据
2. 关闭当前对象
3. 创建一个新的子对象

你可以通过将适当的文本附加到正在构建的 JSON 字符串上来轻松地执行这三个操作，而你迭代源数组以生成你期望的输出所显示的文本。完成后，运行该 JSON 字符串通过 eval。如果输入中存在错误，则可能需要一些安全检查来验证每个数组和对象是否正确关闭，但它应该可以正常工作。

想法 #2

你仍然可以使用你的堆栈数组。我不确定为什么你需要通过引用传递，但你可以只传递一个索引到数组中，并通过索引让每个人修改主副本数组。使用本地函数，主数组可以是一个公共数据值，它是你主要函数的局部变量，但对于所有子函数来说基本上是全局的，因此它们都可以共享访问。

这看起来应该像这样：

function ParseRawData(rawData)
{
    var parentScopeArray = [];   // main parent scope of objects

    function processTag(x)
    {
        // you can access parentScopeArray directly here and
        // and be accessing it by reference
    }

    // other code or local functions here

}

想法 #3

如果你想将数组传递到一个函数中，并修改主副本（也许你考虑的是通过引用传递的原因），那么 JavaScript 的设计模式是将数组传递进去并返回一个修改后的数组，用返回的修改后的数组替换整个原始数组。

- jfriend00

---

好主意 - 谢谢。我会试一下并告诉你结果 :) - Christopher

JSON的想法似乎很容易实现。但是我对第二个想法有一个问题——你打算如何访问不确定（可能无限）嵌套深度的树中的特定数组索引？访问三级深度的项目需要使用类似于tree[0]["children"][7]["children"][2]["children"]的符号表示。除了eval（呕吐）或迭代（缺乏传递引用使其非常困难）之外，我不确定你如何实现这一点。 - Christopher

我认为我的最爱是第二个，我添加了一些伪代码，并利用了Javascript中一些其他语言不提供的有用功能。 - jfriend00

别误会 - 我 喜欢 #2 并且想要使用它 - 只是不确定该怎么做 ;) - Christopher

我现在明白你在问什么了。你可以通过一系列数组索引访问树中的任何父节点。在你之前评论中提到的例子中，它是0,7,2。对“children”属性的引用是隐含的并且始终相同。因此，您可以使用索引数组将任何位置保存到数据结构中。因此，当您创建一个新级别时，将一个新索引添加到该数组的末尾(push)。当您在当前级别上添加新项时，递增数组中最后一个值。完成级别时，从数组中弹出最后一个值。 - jfriend00

只需使用索引数组0,7,2，您就可以构建对数据结构的访问：tree[0]["children"][7]["children"][2]["children"]，并且可以引用数据结构中的任何项。如果您仔细想想，实际上您的数据结构中的数据只是一个数组的数组。您在其中有一个对象只是为了给您提供令牌名称，但实际数据只是一个数组的数组，这使得更容易看到对任何项的引用只是一个数组索引列表。 - jfriend00