聊聊字符串轉(zhuǎn)樹(shù)結(jié)構(gòu)
前言
有一個(gè)多行字符串，每行開(kāi)頭會(huì)用空格來(lái)表示它的層級(jí)關(guān)系，每間隔一層它的空格總數(shù)為2，如何將它轉(zhuǎn)為json格式的樹(shù)型數(shù)據(jù)？本文就跟大家分享下這個(gè)算法，歡迎各位感興趣的開(kāi)發(fā)者閱讀本文。
例如有一個(gè)字符串：
const text = `
Language
JavaScript
TypeScript
NodeJS
HTML
Server
DataBase
MongoDB
System
Linux
Window
`;
將其轉(zhuǎn)換為有層次結(jié)構(gòu)的json數(shù)據(jù)后為：
{
"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"
}
]
}
]
}
思路分析
乍一看，要對(duì)字符串進(jìn)行處理，好像沒(méi)有什么比較好的方法，理不出頭緒。當(dāng)我們遇到這種直接從數(shù)據(jù)結(jié)構(gòu)出發(fā)想不出辦法的問(wèn)題時(shí)，這時(shí)可能就要換個(gè)思路了，能否將它轉(zhuǎn)換為另一種數(shù)據(jù)結(jié)構(gòu)呢？
審題后發(fā)現(xiàn)，我們需要的數(shù)據(jù)元素在字符串中總是獨(dú)占一行的，那么我們就要對(duì)每一行進(jìn)行處理，此時(shí)最好的方式就是將它切割成數(shù)組。
那么，我們就以換行符作為切割點(diǎn)來(lái)構(gòu)造數(shù)組，如下所示：
[
"","Language"," JavaScript", " TypeScript"," NodeJS", " HTML","Server"," DataBase"," MongoDB","System"," Linux"," Window",""
]
觀察數(shù)組中的每個(gè)元素后，我們發(fā)現(xiàn)最頂層的數(shù)據(jù)開(kāi)頭無(wú)空格，每間隔一層，開(kāi)頭就會(huì)多兩個(gè)空格。按照從前往后的順序依次讀取數(shù)據(jù)，將后一個(gè)數(shù)據(jù)與其之前的數(shù)據(jù)進(jìn)行比較，進(jìn)而確定他們之間的層次關(guān)系。
分析到這里，相信很多開(kāi)發(fā)者已經(jīng)看出了這個(gè)比較方式滿足了“后入先出”原則，因此，我們可以用棧來(lái)解決這個(gè)問(wèn)題，如下所示：
- 準(zhǔn)備2個(gè)棧，一個(gè)用于存放每層的字符串，另一個(gè)用于存放每層的空格數(shù)。
- 默認(rèn)將root入棧，將它的空格數(shù)定為-1。
接下來(lái)，我們將每個(gè)元素逐一入棧，分析下它的過(guò)程。如下圖所示，我們列舉了部分元素的入棧比對(duì)過(guò)程，通過(guò)觀察后，總結(jié)出了如下幾條規(guī)律。
- 獲取入棧元素的空格總數(shù)
- 獲取棧頂（deepStack）元素，判斷入棧元素的空格總數(shù)是否大于棧頂元素。
滿足條件則獲取strStack的棧頂元素，將入棧元素元素放入它的子級(jí)
否則，將兩個(gè)棧的元素依次出棧。直至入棧元素的空格總數(shù)比deepStack的棧頂元素大，獲取strStack的棧頂元素，將入棧元素元素放入它的子級(jí)
- 將入棧元素以及它的空格總數(shù)分別放入對(duì)應(yīng)的棧中
- 直至所有元素都入棧比對(duì)完成，此問(wèn)題得到解決
注意：為了讓讀者更直觀的看出規(guī)律，strStack棧中的元素用字符串直接代替了，實(shí)際上棧中存儲(chǔ)的數(shù)據(jù)是一個(gè)對(duì)象，該對(duì)象包含了name屬性和children屬性。當(dāng)前入棧元素也會(huì)構(gòu)造成一個(gè)對(duì)象，得出棧頂元素（deepStack）與入棧元素空格總數(shù)的比對(duì)結(jié)果后，會(huì)將入棧元素對(duì)象放進(jìn)棧頂元素（strStack）的children中。
實(shí)現(xiàn)代碼
經(jīng)過(guò)上面的分析，我們已經(jīng)得出了完整的實(shí)現(xiàn)思路，接下來(lái)我們來(lái)看下代碼的實(shí)現(xiàn)。
/**
* 字符串轉(zhuǎn)樹(shù)結(jié)構(gòu)
* @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;
// 獲取空格總數(shù)
const len = str.lastIndexOf(" ") + 1;
str = str.replace(/\s/g, "");
const curObj = { name: str };
// 尋找當(dāng)前入棧元素的父層級(jí)
while (len <= deepStack.peek()) {
deepStack.pop();
strStack.pop();
}
const stackTop: nodeObj = strStack.peek();
stackTop.children
? stackTop.children.push(curObj)
: (stackTop.children = [curObj]);
// 元素入棧，繼續(xù)下一輪的比對(duì)
strStack.push(curObj);
deepStack.push(len);
}
return json;
}
注意：上述代碼中聲明了一個(gè)自定義類型nodeObj以及一個(gè)自定義類Stack，完整代碼請(qǐng)?jiān)谑纠a中查看。
最后，我們將開(kāi)頭的例子代入上述代碼中，校驗(yàn)下它能否正確解決問(wèn)題。
const text = `
Language
JavaScript
TypeScript
NodeJS
HTML
Server
DataBase
MongoDB
System
Linux
Window
`;
const textJSON = DataConversion(text);
console.log(JSON.stringify(textJSON));
示例代碼
本文用到的代碼完整版請(qǐng)移步：
- DataConversion.ts
- DataConversion-test.ts
