原文：从一道面试题谈起，作者：360奇舞团 刘观宇
题目：
创建一个函数来判断给定的表达式中的大括号是否闭合，返回 true/false，对于空字符串，返回 true
var expression = "{{}}{}{}"
var expressionFalse = "{}{{}"
function isBalanced (exp) {}
题目本身比较简单。看完文章实现，感觉实现思路很重要，更要能举一反三。
虽然大学的时候也学了数据结构，栈，但应用的很少，看完本文，对栈在实际工作中的应用，也有了全新的思路与看法。
实现
以下是应用数据结构栈的特点，先进先出，在 js 中用数组模拟实现的代码。
function isBalanced (exp) {
if (!(exp + '').trim()) {
return true;
}
let stack = [];
let arr = exp.trim().split('');
for (let i = 0; i < arr.length; i++) {
let item = arr[i];
if (item === '{') {
stack.push(item);
} else if (item === '}') {
if (!stack.length) {
return false;
}
stack.pop();
}
}
return stack.length === 0
}
// test
var expT = '{{}}{}{}';
var expF = '{}{{}'
console.log(isBalanced('')); // true
console.log(isBalanced(expT)); // true
console.log(isBalanced(expF)); // false
利用栈先进先出的特点，找到一个 { ，就压入栈中；而找到一个 } ，如栈中是空的，则直接返回false，否则就从栈中弹出一个 { 。循环结束后，通过判断栈是否为空，判断字符中中 {} 是否闭合。
举一反三
题目一：实现函数 isBalanced, 用 true/false 表示给定的字符串的括号是否平衡（一一对应）。注意要支持三种类型的括号，带有交错括号的字符串应该返回false
isBalanced('(foo { bar (baz) [boo] })') // true
isBalanced('foo { bar { baz }') // false
isBalanced('foo { (bar [baz] } )') // true
实现思路和上面的是一致的，也是利用栈的特性。
过滤无效字符，每一种有括号有一种唯一的左括号与之对应。
实现：
function isBalanced (exp) {
if (!(exp + '').trim()) {
return true;
}
let stack = [];
let signObj = {
'{': '}',
'(': ')',
'[': ']'
};
let arr = exp.trim().split('');
for (let i = 0; i < arr.length; i++) {
let item = arr[i];
if (signObj.hasOwnProperty(item)) { // stack 中只压入指定符号
stack.push(item);
} else if (Object.values(signObj).includes(item)) { // 针对指定符号的值比对，得到对象key
let leftSign;
for(let key in signObj) {
if (item === signObj[key]) {
leftSign = key;
}
}
if (stack[stack.length - 1] !== leftSign) {
return false;
}
stack.pop();
}
}
return stack.length === 0;
}
// test
console.log(isBalanced('')); // true
console.log(isBalanced('(foo { bar (baz) [boo] })')); // true
console.log(isBalanced('foo { bar { baz }')); // false
console.log(isBalanced('foo { (bar [baz] } )')); // false
通过对象的键值对过滤掉无效字符，再通过值找到对应的key，和栈中最后压入的进行比较，不相等就是不匹配直接false，相等就表示匹配，然后把栈中的最后的弹出。
通过map和es6的语法，可以把代码写的一气呵成。
function isBalanced (exp) {
if (!(exp + '').trim()) {
return true;
}
const map = new Map([
['{', '}'],
['(', ')'],
['[', ']']
]);
let stack = [];
let arr = exp.trim().split('');
for (let i = 0; i < arr.length; i++) {
let item = arr[i];
if (map.has(item)) {
stack.push(item);
} else if ([...map.values()].includes(item)) {
if (stack[stack.length - 1] !== [...map.entries()].filter(el => el[1] === item).pop().shift()) {
return false;
}
stack.splice(stack.length - 1, 1);
}
}
return stack.length === 0
}
说明：[...map.entries()]的结果是二维数组，这个看懂了，就比较容易理解了
[
['{', '}'],
['(', ')'],
['[', ']']
]
题目二：要求严格限制括号的顺序，即中括号外围只能是大括号，内部只能是小括号。也即：括号只能以大括号、中括号、小括号的顺序只能前面的包含后面的，不能后面的包含前面的，用代码来表示一下
isStrictBalanced('foo { bar (baz) [boo] }') // true
isStrictBalanced('(foo { bar (baz) [boo] })') // false
实现思路，在入栈的时候判断优先级。
怎么判断优先级，利用字符比较。这是我没想到的，都不知道这三个的具体charCodeAt值。(_)
"{".charCodeAt() === 123，"[".charCodeAt() === 91，"(".charCodeAt() === 40
实现：
function isBalanced (exp) {
if (!(exp + '').trim()) {
return true;
}
let stack = [];
let signObj = {
'{': '}',
'[': ']',
'(': ')'
};
let keys = Object.keys(signObj);
let arr = exp.trim().split('');
for (let i = 0; i < arr.length; i++) {
let item = arr[i];
if (signObj.hasOwnProperty(item)) {
// stack 中只压入指定符号，并且判断优先级
// "{".charCodeAt() === 123，"[".charCodeAt() === 91，"(".charCodeAt() === 40
if (stack.length) {
let pop = stack.slice().pop()
if (pop < item) {
return false
}
}
stack.push(item);
} else if (Object.values(signObj).includes(item)) { // 针对指定符号的值比对
let leftSign;
for(let key in signObj) {
if (item === signObj[key]) {
leftSign = key;
}
}
if (stack[stack.length - 1] !== leftSign) {
return false;
}
stack.pop();
}
}
return stack.length === 0;
}
// test
console.log(isBalanced('')); // true
console.log(isBalanced('foo { bar (baz) [boo] }')); // true
console.log(isBalanced('(foo { bar (baz) [boo] })')); // false
console.log(isBalanced('(foo [bar])')); // false
console.log(isBalanced('[foo (bar)]')); // true
console.log(isBalanced('[foo (bar)] {bar [boo] }')); // true
思路通了，用map和es6实现其实也很容易，就不浪费笔墨了。