[[402509]]

在講解這道題之前我們先來看下一個數據結構：棧，因為我們需要用棧來解決這道題。

棧

棧(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); 

 ~完，我是小智，我們下期見~