js 算法 有效的 成对的 括号

算法题目

实现一个算法,能判断出给出的括号串是否是有效的括号对?

比如以下是有效的括号对:
‘()’
‘{}’
‘[]’
‘(){}[]’
‘{()[]}()’
‘’

以下是无效的括号对:
‘)(‘
‘}{‘
‘({)}’
‘({})][‘

主要是成对的左右括号可以正确的顺序闭合出现,则是有效的括号对
我们假设空字符串也是一种有效的括号对

算法详解

这题也是非常常见的算法面试题目,也是比较基础的

计算机专业本科学习数据结构–栈,就有练习是关于括号对,也有关于算术题计算器的
其实都是关于【栈】数据结构的题目的

首先我们还是得先了解下题目什么是有效的括号对?
当相同的左右括号对可以顺序的闭合,则是有效的括号对

尤其‘[(]){}’这就不是一个有效的括号对,因为 [ ( ] ) 并没有形成有效的顺序闭合

那我们看下如何通过算法来判断是否是有效的括号对?

如果是这种括号串 ‘()’ 、‘(){}{}{}()’ ,都是顺序的闭合的,那就很简单,只需要遍历字符串,判断相邻字符串是否成对,( 对应 ),当然,我们不能做这种愚蠢的假设,因为字符串肯定是各种嵌套的
‘( [ ] ) { }’

我们的算法思想是:
1、循环遍历字符串
2、循环过程种每次把当前字符和栈顶字符比较
3、如果是成对关系,比如栈顶是 ‘(‘ 当前字符是 ‘)’,或者栈顶是 ‘{‘ 当前字符是 ‘}’ ,或者栈顶是 ‘[‘ 当前字符是 ‘]’,则栈顶元素出栈(因为形成了成对关系),继续下一个字符遍历
4、如果不是成对关系,除【3】之外的其他所有情形都是有效的成对关系,说明此时并没有形成成对关系,则把当前字符【压栈】– 也就是把当前字符添加到栈种
5、不断重复以上过程,直到字符串遍历结束。
6、如果此时栈为空,则说明是有效的括号对;否则,说明是无效的括号对

(自己用以上字符串,去测试算法过程,帮助你理解)

下面我们看下大概的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function judge(str) {
// 用数组来模拟下栈,栈顶是下标索引高位,栈底是下标索引 0
let stack = []

for (let i = 0; i < str.length; ++ i) {
if (stack.length === 0) {
stack.push(str[i])
} else if (stack[stack.length - 1] === '(' && str[i] === ')') {
stack.pop()
} else if (stack[stack.length - 1] === '[' && str[i] === ']') {
stack.pop()
} else if (stack[stack.length - 1] === '{' && str[i] === '}') {
stack.pop()
} else {
stack.push(str[i])
}
}

return stack.length === 0 ? true : false
}

找几条数据测试下:

1
2
3
4
judge('[()]{}') // true
judge('') // true
judge(')(') // false
judge('[[]()]{}') // true

当然,实现这个算法还有很多其他方式,这里只是借助了栈的这样数据结构

 
更多前端面试题和算法题,请搜索微信小程序 前端面试精华
前端面试精华
前端面试精华

坚持原创技术分享,您的支持将鼓励我继续创作!