TypeScript将带层级空格字符串转换为JSON树结构算法解析

前言

面对一个包含多行文本的字符串，其中每行开头的空格数量用于标识层级关系，且层级间隔固定为2个空格。我们的目标是将这种文本格式转换为具有层级结构的JSON树形数据。本文将详细分享实现该转换的算法逻辑，欢迎感兴趣的开发者阅读。

例如，存在如下格式的字符串：

const text = `
Language
  JavaScript
    TypeScript
    NodeJS
  HTML
Server
  DataBase
    MongoDB
System
  Linux
  Window
`;

经过转换后，生成的具有层级结构的JSON数据如下：

{
    "name":"root",
    "children":[
        {
            "name":"Language",
            "children":[
                {
                    "name":"JavaScript",
                    "children":[
                        {
                            "name":"TypeScript"
                        },
                        {
                            "name":"NodeJS"
                        }
                    ]
                },
                {
                    "name":"HTML"
                }
            ]
        },
        {
            "name":"Server",
            "children":[
                {
                    "name":"DataBase",
                    "children":[
                        {
                            "name":"MongoDB"
                        }
                    ]
                }
            ]
        },
        {
            "name":"System",
            "children":[
                {
                    "name":"Linux"
                },
                {
                    "name":"Window"
                }
            ]
        }
    ]
}

思路分析

直接处理字符串往往缺乏清晰的方法，容易陷入思维僵局。当直接从数据结构角度难以找到解决方案时，可以尝试转换思路：是否可以先将其转换为另一种更易处理的数据结构？

分析题目可知，字符串中的每个数据元素独占一行。因此，处理每一行是最佳切入点，最直观的方式是将字符串切割为数组。

我们可以以换行符作为分割点，将字符串构造为数组，结果如下所示：

[
  "","Language","  JavaScript", "    TypeScript","    NodeJS",   "  HTML","Server","  DataBase","    MongoDB","System","  Linux","  Window",""
]

观察数组中的元素发现，顶层数据开头没有空格，每增加一层，开头便多出两个空格。按照从前到后的顺序读取数据，将当前数据与之前的数据进行比较，从而确定它们之间的层级关系。

分析至此，许多开发者可能已经发现这种比较方式符合“后入先出”的原则。因此，我们可以利用栈结构来解决此问题，具体实现如下：

准备两个栈：一个用于存放每层的字符串节点，另一个用于存放每层对应的空格数量。
默认将根节点（root）入栈，并将其空格数初始化为-1。

接下来，我们将每个元素逐一入栈，并分析其处理过程。如下图所示，列举了部分元素的入栈比对过程，通过观察总结出以下规律。

首先，获取当前入栈元素的空格总数。

获取栈顶元素（deepStack），判断当前入栈元素的空格总数是否大于栈顶元素的空格数。

若满足条件，则获取strStack的栈顶元素，将当前入栈元素放入该栈顶元素的子级（children）中。
若不满足条件，则依次将两个栈的元素出栈，直到当前入栈元素的空格总数大于deepStack的栈顶元素。此时，获取strStack的栈顶元素，将当前入栈元素放入其子级中。

最后，将当前入栈元素及其空格数分别放入对应的栈中。

当所有元素都完成入栈比对后，问题即得到解决。

注意：为了直观展示规律，strStack栈中的元素在示例中直接用字符串表示。实际上，栈中存储的是对象，该对象包含name属性和children属性。当前入栈元素也会被构造成一个对象，在得出栈顶元素（deepStack）与入栈元素空格数的比对结果后，将入栈对象放入栈顶元素（strStack）的children数组中。

实现代码

经过上述分析，我们已经得出了完整的实现思路。接下来，我们查看具体的代码实现。

/**
 * 字符串转树结构
 * @param text
 * @constructor
 */
export function DataConversion(text: string): nodeObj {
  const splitArr = text.split("\n");

  const json = { name: "root" };
  const strStack = new Stack();
  const deepStack = new Stack();
  strStack.push(json);
  deepStack.push(-1);

  for (let i = 0; i < splitArr.length; i++) {
    let str = splitArr[i];
    if (!str) continue;
    // 获取空格总数
    const len = str.lastIndexOf(" ") + 1;
    str = str.replace(/\s/g, "");
    const curObj = { name: str };

    // 寻找当前入栈元素的父层级
    while (len <= deepStack.peek()) {
      deepStack.pop();
      strStack.pop();
    }
    const stackTop: nodeObj = strStack.peek();
    stackTop.children
      ? stackTop.children.push(curObj)
      : (stackTop.children = [curObj]);

    // 元素入栈，继续下一轮的比对
    strStack.push(curObj);
    deepStack.push(len);
  }

  return json;
}

注意：上述代码中声明了一个自定义类型nodeObj以及一个自定义类Stack，完整代码请在示例代码中查看。

最后，我们将开头的示例代入上述代码中，验证其能否正确解决问题。

const text = `
Language
  JavaScript
    TypeScript
    NodeJS
  HTML
Server
  DataBase
    MongoDB
System
  Linux
  Window
`;

const textJSON = DataConversion(text);
console.log(JSON.stringify(textJSON));

示例代码

本文用到的代码完整版请移步：

DataConversion.ts

DataConversion-test.ts

到此这篇关于TypeScript实现字符串转树结构的方法详解的文章就介绍到这了，更多相关TypeScript字符串转树结构内容请搜索本站以前的文章或继续浏览下面的相关文章，希望大家以后多多支持本站！

TypeScript实现字符串转树结构的方法详解

前言

思路分析

实现代码

示例代码

实用工具推荐