第313题(2020-09-26)：编写一个算法解析以下符号，转换为json树的结构 （美团）

[qappleh]

interface TNode {
  name: string;
  children: TNode[] | null;
}

const startTagReg: RegExp = /\<(\w+)\>/; // 匹配开始标签
const endTagReg: RegExp = /\<\/(\w+)\>/; // 匹配结束标签
const closeSelfTagReg: RegExp = /\<(\w+)\/\>/; // 匹配自闭合标签
const textNodeReg: RegExp = /\>(.*?)\<\//; // 匹配文本内容
const tagReg: RegExp = /\<\/?(\w+)\/?\>/g; // 全局匹配标签

let matchedTags: string[] = str.match(tagReg); // 在字符串中匹配到的标签数组

let htmlTree: TNode = null; // 保存生成的节点树
let nodeStacks: TNode[] = []; // 保存遍历过程中的节点栈
let currentNode: TNode | undefined = undefined;

// 根据标签创建新节点
function createNode(tag: string): TNode {
  const tagName = tag.replace(tagReg, "$1");
  return {
    name: tagName,
    children: null
  };
}
// 将节点插入到当前操作栈的节点中
function insertNode(node: TNode) {
  if (htmlTree === null) {
    htmlTree = node;
  } else {
    if (currentNode.children === null) {
      currentNode.children = [node];
    } else {
      currentNode.children.push(node);
    }
  }
}

for (let tag of matchedTags) {
  if (startTagReg.test(tag)) {
    // 创建新节点
    const node = createNode(tag);
    // 向树插入新节点
    insertNode(node);
    // 压入栈，并进入该栈
    nodeStacks.push(node);
    currentNode = nodeStacks[nodeStacks.length - 1];
  } else if (endTagReg.test(tag)) {
    // 找栈中的相对应的节点索引
    let index = nodeStacks
      .reverse()
      .findIndex(el => el.name === tag.replace(tagReg, "$1"));
    index = nodeStacks.length - index;
    nodeStacks.reverse();
    // 删除索引外的栈
    nodeStacks.splice(index - 1);
    // 设置删除后的最后一项为当前节点
    currentNode = nodeStacks[nodeStacks.length - 1];
  } else if (closeSelfTagReg.test(tag)) {
    // 创建新节点
    const node = createNode(tag);
    // 插入新节点
    insertNode(node);
    // 自闭合不需要进栈出栈
  }
}

console.log(matchedTags);
console.log(htmlTree);

{
  "name": "xml",
  "children": [
    {
      "name": "div",
      "children": [
        {
          "name": "p",
          "children": [
            {
              "name": "a",
              "children": null
            }
          ]
        },
        {
          "name": "p",
          "children": null
        }
      ]
    }
  ]
}

早上在地铁看到这题给我整懵了，趁快要吃饭的时间赶紧记录下思考过程，结合前些天看源码，就想到利用模拟进栈出栈的思路，并保留最后可操作节点供插入新值。开始标签就创建节点，并进入新栈；结束标签就找最后一个对应开始标签栈，其余移除栈；自闭合标签不需要进栈出栈，直接更新节点就好。

[frankMa-1993]

优秀 加油 我也开始学习算法了 我的太弱鸡了