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

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

栈

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

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

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

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

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

面试题

这是头条和滴滴的一道面试题，题目是这样的：

试编写“智能重复”smartRepeat 函数，实现：

• 将 3[abc] 变为abcabcabc
• 将 3[2[a]2[b]] 变为 aabbaabbaabb
• 将 2[1[a]3[b]2[3[c]4[d]]] 变为abbbcccddddcccddddabbbcccddddcccdddd

不用考虑输入字符串是非法的情况，比如：

• 2[a3[b]]是错误的，应该补一个 1，即 2[1[a]3[b]]
• [abc]是错误的，应该补一个 1，即 1[abc]

大家一看到这题目，应该想到的用递归的方式来做，实际上这道题用递归是比较难的。也是能做，但相比栈，栈的方式会简单的多。

初学者大坑：栈的题目和递归非常像，这类题目给人的感觉都是用递归解题。信心满满动手开始写了，却发现递归怎么都递归不出来。此时就要想到，不是用递归，而是用栈。

这道题目我们可以使用两个栈来解，第一个栈存放数字，第二个栈存放字符串。

这时候可以发现我们指针只需要遍历一次就行了，怎么看？

规则是这样的子：遍历到数字就把数字压栈

然后继续遍历，这时遍历到方括号，或者说是遍历到数字和方括号，那么我们就把另一个栈放入一个空字符串 ''。

然后下移，遇到 3，同样也是压栈：

然后下移，遇到方括号了，压入一个空字符串 ''

然后下移，遇到字母 a，那么遇到字母是什么规则呢，如图中所示：

然后下移，遇到 ],注意，遍历到结束的右大括号的时候，是一个非常重要的时间，那这个规则又是啥呢，如下图所示：

是不是有点看不懂了，那么我们重头在跑一次

然后下移遇到 4[,分别把数字 4 和 空字符串压入：

然后下移遇到 1[,分别把数字 1 和 空字符串压入：

然后下移遇到 b，压入：

然后下移，遇到结束符 ]，分别要 1 和 ‘b’ 弹出来，此时在把 ‘b’ 重复一遍后拼接到第二个栈顶元素：

然后下移，遇到 2，同样的操作：

然后下移遇到 c，直接写入：

然后下移，遇到结束符 ]，分别把 2 和 ‘c’，弹出，此时在把 ‘c’ 重复二遍后拼接到第二个栈顶元素

然后下移，遇到倒数第二个结束符 ]，分别把 4 和 ‘bccc’，弹出，此时在把 ‘bccc’ 重复四四遍后拼接到第二个栈顶元素：

然后下移，遇到最后一个结束符 ]，分别把 2 和 ‘aaabccbccbccbcc’，弹出，此时在把 ‘aaabccbccbccbcc’ 重复两遍，这时个就不用拼到上一个元素了，因为已经是最后一个了：

这个答案是不是就是我们最后的答案了，神奇吧~

这时个我们在按上面的流程来演示一上这题：

2[1[a]3[b]2[3[c]4[d]]] 变为abbbcccddddcccddddabbbcccddddcccdddd。

代码实现

创建 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);