iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 7
2
Software Development

使用JavaScript學習資料結構與演算法系列 第 7

Day7-利用堆疊解決"平衡括號"問題

這次我們要用昨天學到的堆疊來解決以下問題:

括號分為以下三種: () [] {}
假如一個字串的括號都有與開口(包括: ( [ { )對應的閉合符號(包括: ) ] } )出現,則代表這個字串是平衡的。
例如:
{tall: 177} 為平衡
({123}444) 為平衡
{go[hihi)}) 不為平衡
add({) 不為平衡

主要問題就是將要判斷的字串放入一個函式作判斷,若為平衡就回傳true,不平衡就回傳false


了解問題之後就來實作吧,那麼我們一開始先宣告兩個函式:
peek代表尋找堆疊最上面的元素,而isBalanced會回傳判斷的字串是否平衡。

function peek(stack) {
  return stack[stack.length - 1]
}

function isBalanced(str) {

}

接著去思考如何去判斷字串是否平衡,可以這樣想:

  1. 將字串進行遍歷,當括號是開口型的括號就放到堆疊
  2. 若是閉合型的括號和堆疊最上方元素為一對的括號,如()[]{},就把堆疊最上方元素pop出去
  3. 遍歷到最後,如果堆疊為空,代表此字串是平衡的,回傳true,反之亦然

因此我們可以先將函式寫成這樣:
然後定義兩個變數,OPENING 和 CLOSEING,分別記錄開口和閉合的括號,當遍歷到的元素有在OPENING的字串內,代表是開口的括號,推入堆疊

但如果是閉合的符號的話,判斷堆疊最上面元素在OPENING的索引位置是否和閉合符號在CLOSEING的索引位置一樣

假如兩個位置數字一樣,就進行pop,如果不一樣,代表這個字串肯定不平衡,回傳false結束迴圈

OPENING.indexOf('('): 0
OPENING.indexOf('['): 1
OPENING.indexOf('{'): 2
CLOSEING.indexOf(')'): 0
CLOSEING.indexOf(']'): 1
CLOSEING.indexOf('}'): 2
function isBalanced(str) {
  let stack = []
  let OPENING = '([{'
  let CLOSEING = ')]}'

  for (let i = 0; i < str.length; i++) {
    // 當遍歷到的元素有在OPENING的字串內,代表是開口的括號,推入堆疊
    if (OPENING.includes(str[i])) {
      stack.push(str[i])
    } else if (CLOSEING.includes(str[i])) {
      // 如果是閉合的符號的話,判斷堆疊最上面元素在OPENING的位置是否和閉合符號在CLOSEING的位置一樣
      let top = peek(stack);
      if (OPENING.indexOf(top) === CLOSEING.indexOf(str[i])) {
        stack.pop();
      } else {
        return false;
      }
    }
  }
  // 當字串長度等於0的情況
  return stack.length === 0
}

完整程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day7-bracket-balance.js

明天,將會來介紹佇列喔!


上一篇
Day6-來了解堆疊並實作它吧!
下一篇
Day8-來了解佇列並實作它吧!
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言