[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.首先使用栈时候由于他进出的都是在'栈首',这种问题如果一下都存进栈中，在都取出来实际是无用操作，
因此吧需要的加入栈中，遇到相似的在从栈中弹出来和元素想比较
~~~
- 接触数据结构和算法
- 数据结构与算法 -- 大O复杂度表示法
- 数据结构与算法 -- 时间复杂度分析
- 最好、最坏、平均、均摊时间复杂度
- 基础数据结构和算法
- 线性表和非线性表
- 结构 -- 数组
- JS -- 数组
- 结构 -- 栈
- JS -- 栈
- JS -- 栈有效圆括号
- JS -- 汉诺塔
- 结构 -- 队列
- JS -- 队列
- JS -- 双端队列
- JS -- 循环队列
- 结构 -- 链表
- JS -- 链表
- JS -- 双向链表
- JS -- 循环链表
- JS -- 有序链表
- 结构 -- JS 字典
- 结构 -- 散列表
- 结构 -- js 散列表
- 结构 -- js分离链表
- 结构 -- js开放寻址法
- 结构 -- 递归
- 结构 -- js递归经典问题
- 结构 -- 树
- 结构 -- js 二搜索树
- 结构 -- 红黑树
- 结构 -- 堆
- 结构 -- js 堆
- 结构 -- js 堆排序
- 结构 -- 排序
- js -- 冒泡排序
- js -- 选择排序
- js -- 插入排序
- js -- 归并排序
- js -- 快速排序
- js -- 计数排序
- js -- 桶排序
- js -- 基数排序
- 结构 -- 算法
- 搜索算法
- 二分搜索
- 内插搜索
- 随机算法
- 简单
- 第一题 两数之和
- 第七题 反转整数
- 第九题 回文数
- 第十三题 罗马数字转整数
- 常见一些需求
- 把原始 list 转换成树形结构