何谓平衡括号问题?
平衡括号也叫有效括号,问题描述有很多种,看下面中的一种描述:
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
解决此问题需要借助栈的知识,如下:
引入创建好的 Stack 类。
代码实现如下:
// symbols 为传入的字符串
function parenthesesChecker(symbols) {
// 创建 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 的方式,其他的描述方式解决方法也不一样,这里只是提供一个解决思路作为参考。