TypeScript實現字符串轉樹結構的方法詳解

更新時間：2022年09月26日 08:52:25 作者：神奇的程序員

有一個多行字符串，每行開頭會用空格來表示它的層級關系，每間隔一層它的空格總數為2，如何將它轉為json格式的樹型數據？本文就跟大家分享下這個算法

前言

有一個多行字符串，每行開頭會用空格來表示它的層級關系，每間隔一層它的空格總數為2，如何將它轉為json格式的樹型數據？本文就跟大家分享下這個算法，歡迎各位感興趣的開發(fā)者閱讀本文。

例如有一個字符串：

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"
                }
            ]
        }
    ]
}

思路分析

乍一看，要對字符串進行處理，好像沒有什么比較好的方法，理不出頭緒。當我們遇到這種直接從數據結構出發(fā)想不出辦法的問題時，這時可能就要換個思路了，能否將它轉換為另一種數據結構呢？

審題后發(fā)現，我們需要的數據元素在字符串中總是獨占一行的，那么我們就要對每一行進行處理，此時最好的方式就是將它切割成數組。

那么，我們就以換行符作為切割點來構造數組，如下所示：

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

觀察數組中的每個元素后，我們發(fā)現最頂層的數據開頭無空格，每間隔一層，開頭就會多兩個空格。按照從前往后的順序依次讀取數據，將后一個數據與其之前的數據進行比較，進而確定他們之間的層次關系。

分析到這里，相信很多開發(fā)者已經看出了這個比較方式滿足了**“后入先出”**原則，因此，我們可以用棧來解決這個問題，如下所示：

準備2個棧，一個用于存放每層的字符串，另一個用于存放每層的空格數
默認將root入棧，將它的空格數定為-1

接下來，我們將每個元素逐一入棧，分析下它的過程。如下圖所示，我們列舉了部分元素的入棧比對過程，通過觀察后，總結出了如下幾條規(guī)律。

獲取入棧元素的空格總數

獲取棧頂（deepStack）元素，判斷入棧元素的空格總數是否大于棧頂元素。

滿足條件則獲取strStack的棧頂元素，將入棧元素元素放入它的子級
否則，將兩個棧的元素依次出棧。直至入棧元素的空格總數比deepStack的棧頂元素大，獲取strStack的棧頂元素，將入棧元素元素放入它的子級

將入棧元素以及它的空格總數分別放入對應的棧中

直至所有元素都入棧比對完成，此問題得到解決

注意：為了讓讀者更直觀的看出規(guī)律，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]);

    // 元素入棧，繼續(xù)下一輪的比對
    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));