正则小应用:括号嵌套问题
今天看到一道题,要实现一个函数,判断给定字符串中的大中小括号是否是正确嵌套。
比如:
"([[some](){text}here]...)" => true
"{([])}" => true
"()[]{}()" => true
"(...[]...{(..())}[abc]())" => true
"1239(df){" => false
"[()])" => false
")12[x]34(" => false
第一眼看到此题时,一个字蹦入脑海:栈!
遇到开括号时,往栈里push。遇到闭括号时,再看其与当前栈顶那个开括号是否匹配。如果匹配的话,那么弹出栈顶。不匹配的话,结论就出来了:整体不是正确嵌套的。假设一直能匹配下去的话,最终看下,栈是否空了。如果栈空,说明不多不少、正好正确嵌套,否则说明开括号多了。
文字看起来啰嗦些,具体请看代码实现:
function bracesStatus(string) {
let stack = [], mapping = { ')': '(', ']': '[', '}': '{' }
for (let c of string) {
if (/[\(\[\{]/.test(c)) {
stack.push(c)
} else if (/[\)\]\}]/.test(c)) {
if (stack.length === 0) return false
if (stack[stack.length - 1] != mapping[c]) {
return false
} else {
stack.pop()
return stack.length === 0
console.log(bracesStatus('([[some](){text}here]...)'))
后来又仔细想了下,用正则实现起来会更简单些。
首先,去掉目标字符串中的非括号字符,剩下的全是括号了,如:
"([[some](){text}here]...)" => "([[](){}])"
然后再不断去掉相邻成对(匹配)的括号,比如:
"([[](){}])" => "([])" => "()" => ""
如果最后变成了空字符,说明是匹配的,否则就是不匹配的。
具体代码实现:
function bracesStatus(string) {
string = string.replace(/[^\(\)\[\]\{\}]/g, '')
while(/\(\)|\[\]|\{\}/.test(string)) {