JS -- 棧有效圓括號 · js數據結構與算法

[TOC] >[success] # 棧的實戰案例 -- 有效圓括號 ~~~ 1.有效圓括號又叫（平衡圓括號）問題，問題描述：給定一個只包括 '('，')'，'{'，'}'，'['，']'?的字符串，判斷字符串是否有效。有效字符串需滿足： 1.1.左括號必須用相同類型的右括號閉合。 1.2.左括號必須以正確的順序閉合。 1.3.注意空字符串可被認為是有效字符串。舉個例子： ([)] -- false [{()] -- false {{([][])}()} -- true ~~~ >[info] ## 思路 ~~~ 1.哪一個為例子'({[]})',將這個按照對稱軸分開會得到'({[' 和 ']})',這時候可以發現左面字符串第一個'(' 是和右面第三個')' 是對稱的，這里如果使用棧的思想'后進先出'，也就是左面'(' 會最先進入棧中，第三個出來，正好和右面')'第三個位置匹配 ~~~ >[danger] ##### 通用代碼創建一個棧 ~~~ 1.當然可以直接用數組，這里只是為了學的棧，數組的話要遵循棧的'先進后出原則'即可 ~~~ ~~~ class Stack { constructor() { this.count = 0; this.items = {}; } push(element) { this.items[this.count] = element; this.count++; } pop() { if (this.isEmpty()) { return undefined; } this.count--; const result = this.items[this.count]; delete this.items[this.count]; return result; } peek() { if (this.isEmpty()) { return undefined; } return this.items[this.count - 1]; } isEmpty() { return this.count === 0; } size() { return this.count; } clear() { /* while (!this.isEmpty()) { this.pop(); } */ this.items = {}; this.count = 0; } toString() { if (this.isEmpty()) { return ''; } let objString = `${this.items[0]}`; for (let i = 1; i < this.count; i++) { objString = `${objString},${this.items[i]}`; } return objString; } } ~~~ >[danger] ##### 最開始錯誤的思路 ~~~ 1.錯誤思路，下面代碼的思路是將情況固有化只考慮對稱的情況，將數據平分，依次保存依次比較，但實際運行的時候'{{([][])}()}' 這種特殊情況沒有考慮進去 ~~~ ~~~ function parenthesesChecker(symbols){ const stack = new Stack() const lSymbols = '({[' const RSymbols = ')}]' const symbolsLen = symbols.length let flag = true let top if(symbolsLen ===0 ){ flag = true }else if(symbolsLen % 2!==0){ flag = false }else{ const symbolsHafLen = symbolsLen/2 for(var i=0,item;item = symbols[i++];){ if(symbolsHafLen <= i-1){ top = stack.pop() if(lSymbols.indexOf(top) !== RSymbols.indexOf( item)){ flag = false break } }else{ stack.push(item) } } } return flag } ~~~ >[danger] ##### 參考書中的方法思路 ~~~ 1.第一點循環不僅僅只有for，我們可以使用while ，這樣可以并列多個循環條件，來控制跳出循環 2.第二點，我們用棧來存儲左面組的括號，當循環時候遇到右面組的括號，應該從棧中取出棧首的，也就是'后入先出的規則'和右面組進行對比 3."()[]{}" '{{([][])}()}' ??? 思考問題 ,把這種大問題拆分成小問題， 3.1.要做的是括號可以閉合，如果我現在取出來的括號，可以和他的對稱面相等說明他是一個閉合 3.2.現在要做的就是如何做到比較A和A的對稱面相等，也就是要證明判斷'(' ')' 相等 3.3.這里采用記錄他們的位置來比較： ({[ -- 左半部分 ){[ -- 右半邊現在來看，也就是右半部分的1等于左半部分1說明是一個有效閉合 3.4.一些特殊情況的考慮比如只有給個'(' 或者')' 或者''當然'' 也算對稱 ~~~ ~~~ export function parenthesesChecker(symbols) { 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; break } else { top = stack.pop(); if (!(opens.indexOf(top) === closers.indexOf(symbol))) { balanced = false; break } } index++; } // 為什么要判斷 stack 為空 // 因為用可能判斷的符號為 '[' 此時會存在棧中 // 如果單單是balanced 為true 但是棧卻有值沒清空，因此必須是空棧才可以 return balanced && stack.isEmpty(); } console.log('[', parenthesesChecker('[')); // false console.log('{([])}', parenthesesChecker('{([])}')); // true console.log('{{([][])}()}', parenthesesChecker('{{([][])}()}')); // true console.log('[{()]', parenthesesChecker('[{()]')); // false ~~~ >[danger] ##### 總結 ~~~ 1.首先使用棧時候由于他進出的都是在'棧首',這種問題如果一下都存進棧中，在都取出來實際是無用操作，因此吧需要的加入棧中，遇到相似的在從棧中彈出來和元素想比較 ~~~