今日kata

原始題目如下:(6kyu)
Write a function that takes a string of braces, and determines if the order of the braces is valid. It should return true if the string is valid, and false if it's invalid.
This Kata is similar to the Valid Parentheses Kata, but introduces new characters: brackets [], and curly braces {}.
All input strings will be nonempty, and will only consist of parentheses, brackets and curly braces: ()[]{}.

翻譯:
有三種括號() [] {} ，需判斷括號格式是否正確、是否成對出現。

範例:

"(){}[]"   =>  True
"([{}])"   =>  True
"(}"       =>  False
"[(])"     =>  False
"[({})](]" =>  False

構想&解法

function validBraces(braces) {
  let stack = []
  let open = '[({'
  let close = '])}'
  for (let i = 0; i < braces.length; i++) {
    if (open.includes(braces[i])) {
      stack.push(braces[i])
    } else {
      let index = close.indexOf(braces[i]);
      if (stack.pop() !== open[index]) return false
    }
  }
  return stack.length === 0 ? true : false
}

宣告open、close儲存([{(開頭括號)及)]}(結尾括號)，並建立一stack陣列。依序檢驗每一個字元，若字元屬於開頭括號之一，則放入stack中；否則取出stack中最後一個元素檢驗是否為相對應開頭括號。

其他寫法觀摩

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

沒錯... 離不開正規表示式，乍看很可怕，是因為三種括號是特殊字元要使用跳脫符號。

使用while loop檢測braces字串中是否有() 或是[] 或是 {}的存在(中間不得有其他字元才符合)，若上述條件符合，則把該組成對括號取代成空字串。最後依據braces長度判斷是否有剩餘括號存在。

function validBraces(braces){
  var matches = { '(':')', '{':'}', '[':']' };
  var stack = [];
  var currentChar;

  for (var i=0; i<braces.length; i++) {
    currentChar = braces[i];

    if (matches[currentChar]) { // opening braces
      stack.push(currentChar);
    } else { // closing braces
      if (currentChar !== matches[stack.pop()]) {
        return false;
      }
    }
  }

  return stack.length === 0; // any unclosed braces left?
}

概念類似，宣告一stack陣列，並將括號種類存至matches物件中(key為開頭括號，value為結尾括號)，for loop遍歷每一個braces中的字元，用這個字元當作property去查詢matches中是否有這個屬性值，進一步判斷要把該字元放入stack中或是return false。

整理

括號類型的題目常利用到stack資料結構的概念來解題，以下簡略整理什麼是資料結構? 還有常使用的資料結構Stack和Queue?

資料結構-Data Structure

當數據儲存在記憶體中時，資料結構負責決定數據的順序和位置。

而所謂變數就是記憶體中的位址，要有效的取用我們所需要的資料前，怎麼存放更是重要。
要怎麼收穫 先怎麼栽

根據目的，有組織的將資料存放在記憶體中，即是資料結構!

常來說明資料結構重要性的例子有:

• 電話簿
• 圖書館藏書

在基於某種需求下，該如何儲存資料，以使未來在取用、存放、刪除資料時，能夠有效執行!

以電話簿為例:

1. 由先後順序存放資料，想像有張表格，欄位分別是姓名和電話，電話資料由上至下一列一列增加。在這種存放的方式，如果要查詢特定人士的電話，只能逐筆查詢。

2. 由姓氏順序存放資料，想像將姓氏當做資料表的索引，在查詢時可由姓氏進行過濾，縮短逐筆查詢的時間。

看似方法二很優，但在新增資料時，方法二所耗費的時間會比方法一多! 方法一直接加在資料的最後就ok，而方法二在增加資料時，要先找到插入的列數，並把後面的資料通通下移一列。

所以電話簿建立後的需求或是使用就很重要，如果較沒那麼頻繁更新，可以使用方法二，如果需要頻繁增加資料但不太需要查詢，可以使用方法一。

折衷的方法也是有的，將姓氏分類分成不同表格存放，然後以先後順序增加資料。

以上範例取自:演算法圖鑑

Stack(堆疊)及 Queue佇列

Stack為先進後出的特性，生活中像是一疊桌上的盤子，先放的盤子在最底下，最後放入的盤子在最上層，要移除盤子一定要從最上層開始。

在Javascript中可以使用arr.push()和arr.pop()來新增元素或是刪除元素，達到先進後出的特性。

圖取自Data Structure with JavaScript: Stacks

Queue為先進先出的特性，生活中像是排隊等待上車的乘客，先排隊的人可以先上車。

在Javascript中可以使用arr.push()和arr.shift()來新增元素或是刪除元素，達到先進先出的特性。
反過來用arr.pop()和arr.unshift()也行!

圖取自The Little Guide of Queue in JavaScript

括號這類型的題目就很適合使用Stack來處理，根據Stack最尾端的元素判斷到底要放入新元素/新括號，還是要移除Stack最尾端的元素/因為成對所以移除。

以上為今日分享的內容，若有錯誤或是建議，請再隨時和我聯繫。