[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.首先使用栈时候由于他进出的都是在'栈首',这种问题如果一下都存进栈中，在都取出来实际是无用操作， 因此吧需要的加入栈中，遇到相似的在从栈中弹出来和元素想比较 ~~~