JavaScript 平衡括號算法

何謂平衡括號問題?
平衡括號也叫有效括號,問題描述有很多種,看下面中的一種描述:

給定一個只包括 '(',')','{','}','[',']' 的字符串,判斷字符串是否有效。
有效字符串需滿足:
1、左括號必須用相同類型的右括號閉合。
2、左括號必須以正確的順序閉合。

解決此問題需要借助棧的知識,如下:

引入創(chuàng)建好的 Stack 類。

代碼實現(xiàn)如下:

// symbols 為傳入的字符串
function parenthesesChecker(symbols) {
  // 創(chuàng)建 Stack 類
  const stack = new Stack();
  // 左括號
  const opens = '([{';
  // 右括號
  const closers = ')]}';
  let balanced = true;
  let index = 0;
  let symbol;
  let top;

  while (index < symbols.length && balanced) {
    symbol = symbols[index];
    // 左括號入棧待匹配
    if (opens.indexOf(symbol) >= 0) {
      stack.push(symbol); 
    } else if (stack.isEmpty()) {
      balanced = false;
    } else {
      // 遇到右括號,出棧匹配
      top = stack.pop();
      if (!(opens.indexOf(top) === closers.indexOf(symbol))) {
        balanced = false;
      }
    }
    index++;
  }
  // 剩下未匹配的左括號,一定是無效的
  return balanced && stack.isEmpty();
}

// test
console.log('([])', parenthesesChecker('([])'));    // ([]) true
console.log('{([])}', parenthesesChecker('{([])}'));    // {([])} true
console.log('(([()])))', parenthesesChecker('(([()])))'));    // (([()]))) false
console.log('([()[]()])()', parenthesesChecker('([()[]()])()'));    // ([()[]()])() true

平衡(有效)括號問題有很多的變形描述,這只是一種,這里的解決思路也是JavaScript 的方式,其他的描述方式解決方法也不一樣,這里只是提供一個解決思路作為參考。

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

  • 第一部分 HTML&CSS整理答案 1. 什么是HTML5? 答:HTML5是最新的HTML標準。 注意:講述HT...
    kismetajun閱讀 28,827評論 1 45
  • 1)這本書為什么值得看: Python語言描述,如果學的Python用這本書學數(shù)據(jù)結構更合適 2016年出版,內(nèi)容...
    孫懷闊閱讀 12,915評論 0 15
  • 第5章 引用類型(返回首頁) 本章內(nèi)容 使用對象 創(chuàng)建并操作數(shù)組 理解基本的JavaScript類型 使用基本類型...
    大學一百閱讀 3,684評論 0 4
  • Unicode?標準附錄#9 UNICODE雙向算法#### 摘要#### 本附件是一份關于字符定位的規(guī)范,主要描...
    Eriice閱讀 5,203評論 0 6
  • 一棹西風生濃愁,參差紅葉暗驚秋。 暮雨瀟瀟孤鴻遠,野藤蒼蒼亂絮悠。 日落鳥鳴腸欲斷,寒霧深沉意難休。 別來幾載鄉(xiāng)關...
    逸塵居士閱讀 271評論 0 0

友情鏈接更多精彩內(nèi)容