栈数据

什么是栈

栈是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数据。

栈就像是一摞书（📚），拿到新书时我们会把它放到书堆的最上面，取书时也只能从最上面的新书开始取。

像栈这种最后添加的数据最先被取出，即 “后进先出” 的结构，我们称之为 Last in First Out （LIFO）

和队列刚好相反，队列数据结构就像排队一样，先排先出 First in First Out （FIFO）。

smartRepeat

function smartRepeat(templateStr) {
  const stackNumber = [];
  const stackWord = [];
  let rest = templateStr;
  let index = 0;
  while (index < templateStr.length - 1) {
    rest = templateStr.substring(index);
    // 先把数字放入数字栈中
    if (/^\d+\[/.test(rest)) {
      // 拿到数字
      const times = Number(rest.match(/^(\d+)\[/)[1]);
      // 数字压栈
      stackNumber.push(times);
      // 字符栈要压一个空字符串
      stackWord.push("");
      // 指针后移：加1是[
      index += times.toString().length + 1;
    } else if (/^\w+\]/.test(rest)) {
      // 拿到文本字符,把文字栈的栈顶压入这个文本（也就是和之前的栈顶的文字拼接）
      const word = rest.match(/^(\w+)\]/)[1];
      stackWord[stackWord.length - 1] = word;
      // 指针后移 word 长度位数
      index += word.length;
    } else if (rest[0] === "]") {
      // 如果是 ] 就表示遇到结束符号，当前数字栈和文字栈需要将栈顶弹出了
      // 将弹出的文字重复弹出的数字的次数，在将已经重复过的文字拼接到栈顶
      const repeatCount = stackNumber.pop();
      const outWord = stackWord.pop();
      // repeat 是es6的方法，表示字符串要重复次数
      const newWord = outWord.repeat(repeatCount);
      stackWord[stackWord.length - 1] += newWord;
      index++;
    }
  }
  return stackWord[0].repeat(stackNumber[0]);
}

const templateStr = "2[3[abc]4[d]5[6e]]";
const result = smartRepeat(templateStr);
console.log(result);