[[402509]]

在講解這道題之前我們先來看下一個數(shù)據(jù)結(jié)構(gòu)：棧，因為我們需要用棧來解決這道題。

棧

棧(stack)又名堆棧，它是一種運(yùn)算受限的線性表，僅在表尾能進(jìn)行插入和刪除操作。這一端被稱為棧頂，相對地，把另一端稱為棧底。

向一個棧插入新元素又稱作進(jìn)棧、入?；驂簵?從一個棧刪除元素又稱作出?；蛲藯?。

后進(jìn)先出(LIFO)特點：棧中的元素，最先進(jìn)棧的必定是最后出棧，后進(jìn)棧的一定會先出棧。

JavaScript中，?？梢杂脭?shù)組模擬。需要限制只能使用push()和pop()，不能使用unshift()和shift()。即，數(shù)組尾是棧頂。

當(dāng)然，可以用面向?qū)ο蟮仁侄?，將棧封裝的更好。

面試題

這是頭條和滴滴的一道面試題，題目是這樣的：

試編寫“智能重復(fù)”smartRepeat函數(shù)，實現(xiàn)：

• 將 3[abc] 變?yōu)閍bcabcabc
• 將 3[2[a]2[b]] 變?yōu)?aabbaabbaabb
• 將 2[1[a]3[b]2[3[c]4[d]]] 變?yōu)閍bbbcccddddcccddddabbbcccddddcccdddd

不用考慮輸入字符串是非法的情況，比如：

2[a3[b]]是錯誤的，應(yīng)該補(bǔ)一個1，即2[1[a]3[b]]

[abc]是錯誤的，應(yīng)該補(bǔ)一個1，即1[abc]

大家一看到這題目，應(yīng)該想到的用遞歸的方式來做，實際上這道題用遞歸是比較難的。也是能做，但相比棧，棧的方式會簡單的多。

**初學(xué)者大坑：**棧的題目和遞歸非常像，這類題目給人的感覺都是用遞歸解題。信心滿滿動手開始寫了，卻發(fā)現(xiàn)遞歸怎么都遞歸不出來。此時就要想到，不是用遞歸，而是用棧。

這道題目我們可以使用兩個棧來解，第一個棧存放數(shù)字，第二個棧存放字符串

這時候可以發(fā)現(xiàn)我們指針只需要遍歷一次就行了，怎么看?

規(guī)則是這樣的子：遍歷到數(shù)字就把數(shù)字壓棧

然后繼續(xù)遍歷，這時遍歷到方括號，或者說是遍歷到數(shù)字和方括號，那么我們就把另一個棧放入一個空字符串 ''。

然后下移，遇到 3，同樣也是壓棧：

然后下移，遇到方括號了，壓入一個空字符串 ''

然后下移，遇到字母 a，那么遇到字母是什么規(guī)則呢，如圖中所示：

然后下移，遇到 ],注意，遍歷到結(jié)束的右大括號的時候，是一個非常重要的時間，那這個規(guī)則又是啥呢，如下圖所示：

然后下移遇到 4[,分別把數(shù)字 4 和 空字符串壓入：

然后下移遇到 1[,分別把數(shù)字 1 和 空字符串壓入：

然后下移遇到 b，壓入：

然后下移，遇到結(jié)束符 ]，分別要 1 和 'b' 彈出來，此時在把 'b' 重復(fù)一遍后拼接到第二個棧頂元素

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

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

然后下移，遇到結(jié)束符 ]，分別把 2 和 'c'，彈出，此時在把 'c' 重復(fù)二遍后拼接到第二個棧頂元素

然后下移，遇到倒數(shù)第二個結(jié)束符 ]，分別把 4 和 'bccc'，彈出，此時在把 'bccc' 重復(fù)四四遍后拼接到第二個棧頂元素

然后下移，遇到最后一個結(jié)束符 ]，分別把 2 和 'aaabccbccbccbcc'，彈出，此時在把 'aaabccbccbccbcc' 重復(fù)兩遍，這時個就不用拼到上一個元素了，因為已經(jīng)是最后一個了：

這個答案是不是就是我們最后的答案了，神奇吧~

這時個我們在按上面的流程來演示一上這題：

2[1[a]3[b]2[3[c]4[d]]] 變?yōu)閍bbbcccddddcccddddabbbcccddddcccdddd。

代碼實現(xiàn)

創(chuàng)建 index.js，輸入以下內(nèi)容：

// 試編寫“智能重復(fù)”smartRepeat函數(shù)，實現(xiàn)： 
// 將3[abc]變?yōu)閍bcabcabc 
// 將3[2[a]2[b]]變?yōu)閍abbaabbaabb 
// 將2[1[a]3[b]2[3[c]4[d]]]變?yōu)閍bbbcccddddcccddddabbbcccddddcccdddd 
 
function smartRepeat(templateStr) { 
  // 指針 
  var index = 0; 
  // 棧1，存放數(shù)字 
  var stack1 = []; 
  // 棧2，存放臨時字符串 
  var stack2 = []; 
  // 剩余部分 
  var rest = templateStr; 
 
  while (index < templateStr.length - 1) { 
    // 剩余部分 
    rest = templateStr.substring(index); 
 
    // 看當(dāng)前剩余部分是不是以數(shù)字和[開頭 
    if (/^\d+\[/.test(rest)) { 
      // 得到這個數(shù)字 
      let times = Number(rest.match(/^(\d+)\[/)[1]); 
      // 就把數(shù)字壓棧，把空字符串壓棧 
      stack1.push(times); 
      stack2.push(""); 
      // 讓指針后移，times這個數(shù)字是多少位就后移多少位加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彈棧，③把字符串棧的新棧頂?shù)脑刂貜?fù)剛剛彈出的那個字符串指定次數(shù)拼接到新棧頂上。 
      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結(jié)束之后，stack1和stack2中肯定還剩余1項。返回棧2中剩下的這一項，重復(fù)棧1中剩下的這1項次數(shù)，組成的這個字符串。如果剩的個數(shù)不對，那就是用戶的問題，方括號沒有閉合。 
  return stack2[0].repeat(stack1[0]); 
} 
 
var result = smartRepeat("3[2[3[a]1[b]]4[d]]"); 
console.log(result); 

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