社区首页 >专栏 >字符串转树结构

字符串转树结构

神奇的程序员

发布于 2022-10-30 06:24:13

3.3K00

代码可运行

文章被收录于专栏：神奇的程序员的专栏神奇的程序员的专栏

运行总次数：0

代码可运行

前言

有一个多行字符串，每行开头会用空格来表示它的层级关系，每间隔一层它的空格总数为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",""
]

观察数组中的每个元素后，我们发现最顶层的数据开头无空格，每间隔一层，开头就会多两个空格。按照从前往后的顺序依次读取数据，将后一个数据与其之前的数据进行比较，进而确定他们之间的层次关系。

分析到这里，相信很多开发者已经看出了这个比较方式满足了“后入先出”原则，因此，我们可以用栈来解决这个问题，如下所示：

准备2个栈，一个用于存放每层的字符串，另一个用于存放每层的空格数
默认将root入栈，将它的空格数定为-1

image-20220923074054521

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

获取入栈元素的空格总数
获取栈顶（deepStack）元素，判断入栈元素的空格总数是否大于栈顶元素。
- 满足条件则获取strStack的栈顶元素，将入栈元素元素放入它的子级
- 否则，将两个栈的元素依次出栈。直至入栈元素的空格总数比deepStack的栈顶元素大，获取strStack的栈顶元素，将入栈元素元素放入它的子级
将入栈元素以及它的空格总数分别放入对应的栈中
直至所有元素都入栈比对完成，此问题得到解决

image-20220925084748469

注意：为了让读者更直观的看出规律，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));