图解头条和滴滴的一道面试题：smartRepeat 函数

1. 栈
2. 面试题
3. 代码实现

在讲解这道题之前我们先来看下一个数据结构：栈，因为我们需要用栈来解决这道题。

栈

栈（stack）又名堆栈，它是一种运算受限的线性表，仅在表尾能进行插入和删除操作。这一端被称为栈顶，相对地，把另一端称为栈底。

向一个栈插入新元素又称作进栈、入栈或压栈；从一个栈删除元素又称作出栈或退栈。

后进先出（LIFO）特点：栈中的元素，最先进栈的必定是最后出栈，后进栈的一定会先出栈。

JavaScript 中，栈可以用数组模拟。需要限制只能使用push()和pop()，不能使用unshift()和shift()。即，数组尾是栈顶。

当然，可以用面向对象等手段，将栈封装的更好。

代码实现

创建 index.js，输入以下内容：

// 试编写“智能重复”smartRepeat 函数，实现：
// 将 3[abc]变为 abcabcabc
// 将 3[2[a]2[b]]变为 aabbaabbaabb
// 将 2[1[a]3[b]2[3[c]4[d]]]变为 abbbcccddddcccddddabbbcccddddcccdddd

function smartRepeat(templateStr) {
  // 指针
  var index = 0;
  // 栈 1，存放数字
  var stack1 = [];
  // 栈 2，存放临时字符串
  var stack2 = [];
  // 剩余部分
  var rest = templateStr;

  while (index < templateStr.length - 1) {
    // 剩余部分
    rest = templateStr.substring(index);

    // 看当前剩余部分是不是以数字和[开头
    if (/^d+[/.test(rest)) {
      // 得到这个数字
      let times = Number(rest.match(/^(d+)[/)[1]);
      // 就把数字压栈，把空字符串压栈
      stack1.push(times);
      stack2.push("");
      // 让指针后移，times 这个数字是多少位就后移多少位加 1 位。
      // 为什么要加 1 呢？加的 1 位是[。
      index += times.toString().length + 1;
    } else if (/^w+]/.test(rest)) {
      // 如果这个字符是字母，那么此时就把栈顶这项改为这个字母
      let word = rest.match(/^(w+)]/)[1];
      stack2[stack2.length - 1] = word;
      // 让指针后移，word 这个词语是多少位就后移多少位
      index += word.length;
    } else if (rest[0] == "]") {
      // 如果这个字符是]，那么就①将 stack1 弹栈，②stack2 弹栈，③把字符串栈的新栈顶的元素重复刚刚弹出的那个字符串指定次数拼接到新栈顶上。
      let times = stack1.pop();
      let word = stack2.pop();
      // repeat 是 ES6 的方法，比如'a'.repeat(3)得到'aaa'
      stack2[stack2.length - 1] += word.repeat(times);
      index++;
    }

    console.log(index, stack1, stack2);
  }

  // while 结束之后，stack1 和 stack2 中肯定还剩余 1 项。返回栈 2 中剩下的这一项，重复栈 1 中剩下的这 1 项次数，组成的这个字符串。如果剩的个数不对，那就是用户的问题，方括号没有闭合。
  return stack2[0].repeat(stack1[0]);
}

var result = smartRepeat("3[2[3[a]1[b]]4[d]]");
console.log(result);