JS括號匹配問題

在codewars上做了一道括號匹配的題目。

題目

判斷字串中的{}、[]、()三種括號是否匹配，需要考慮嵌套的情況。

這個問題的最根本只有兩種情況，一種是並列的，即沒有嵌套的情況，如()[]{};另一種情況就是嵌套的情況，如{[()]}。第一種情況是比較簡單的，有難度的是第二種情況。存在嵌套的情況的解決方法，是先配對最裡面的括號對，也就是我們常說的從內部開始瓦解。

第一種方法：

validBraces("(){}[]")     // true 
validBraces("(}")         // false 
validBraces("[(])")       // false 
validBraces("([{}])")     // true

這種方法，找出成對的括號，然後將成對相鄰的括號替換成空字串，也就是說刪除。最後判斷字串的長度是否為0。是，則表示完全匹配，否則，比匹配。

其實，這種方案就是典型的「從內部開始瓦解」。我們以{[()]}為例，你觀察一下，現在只有最裡面的()才是成對且相鄰的，當把()替換成空字串之後，[]變成了成對且相鄰的，然後再將其替換成空字串。就這樣一直循環地查找，直到再也找不到成對且相鄰的括號為止。

第二種方法：

function validBraces(braces){
  while(/\(\)|\[\]|\{\}/g.test(braces)){
    braces = braces.replace(/\(\)|\[\]|\{\}/g,"")
  }
  return !braces.length;
}

這種方法，是將左半邊括號，即(、[、{存入棧stack中，當遍歷到右半邊括號，即)、]、}的時候，stack執行出棧操作，然後將出棧的左半邊括號與遍歷到的有半邊括號匹配，看是否為與其相匹配的另半邊括號。如果遍歷完了，則判斷棧的長度，為0，則匹配，否則，比匹配。 我們同樣以{[()]}為例，前三項，即{、[、(入棧，當遍歷到)的時候，位於棧頂的'('後出棧與)比較，看是否匹配。後面的]、}也是一樣道理。

結語

現在漸漸發現，資料結構和正規表示式非常重要（這裡的解法就分別用到了），雖然平常用得少，到一道有應用場景，你就會發現資料結構和正規表示式的強大了。