欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

JS括号匹配问题

程序员文章站 2022-05-23 14:08:35
...
在codewars上做了一道括号匹配的题目。

题目

判断字符串中的{}、[]、()三种括号是否匹配,需要考虑嵌套的情况。

例子:

validBraces("(){}[]")     // true 
validBraces("(}")         // false 
validBraces("[(])")       // false 
validBraces("([{}])")     // true

Solution

这个问题的最根本只有两种情况,一种是并列的,即没有嵌套的情况,如()[]{};另一种情况就是嵌套的情况,如{[()]}。第一种情况是比较简单的,有难度的是第二种情况。存在嵌套的情况的解决方法,是首先匹配最里面的括号对,即我们常说的从内部开始瓦解。

第一种方法:

function validBraces(braces){
  while(/\(\)|\[\]|\{\}/g.test(braces)){
    braces = braces.replace(/\(\)|\[\]|\{\}/g,"")
  }
  return !braces.length;
}

这种方法,查找成对的括号,然后将成对相邻的括号替换成空字符串,也就是说删除。最后判断字符串的长度是否为0。是,则表示完全匹配,否则,比匹配。
其实,这种方案就是典型的“从内部开始瓦解”。我们以{[()]}为例,你观察一下,现在只有最里面的()才是成对且相邻的,当把()替换成空字符串之后,[]变成了成对且相邻的,然后再将其替换成空字符串。就这样一直循环地查找,直到再也找不到成对且相邻的括号为止。

第二种方法:

function validBraces(braces){
  let leftBraReg = /[\(\{\[]/, 
    // 栈
      stack = [],
      bracket, rightBracket
  braces = braces.split('')
  for(bracket of braces) {
    if(leftBraReg.test(bracket)) {
      stack.push(bracket)
    }
    else {
      switch (bracket) {
          case ')':
          rightBracket = stack.pop()
          if(rightBracket !=='(') {
              return false
          }
          break
        case ']':
          rightBracket = stack.pop()
          if(rightBracket !=='[') {
              return false
          }
          break
        case '}':
          rightBracket = stack.pop()
          if(rightBracket !=='{') {
              return false
          }
          break
      }
    }
  }
  return stack.length === 0 ? true : false
}

这种方法,是将左半边括号,即(、[、{存入栈stack中,当遍历到右半边括号,即)、]、}的时候,stack执行出栈操作,然后将出栈的左半边括号与遍历到的有半边括号匹配,看是否为与其相匹配的另半边括号。如果遍历完了,则判断栈的长度,为0,则匹配,否则,比匹配。
我们同样以{[()]}为例,前三项,即{、[、(入栈,当遍历到)的时候,位于栈顶的'('后出栈与)比较,看是否匹配。后面的]、}也是一样道理。

结语

现在渐渐发现,数据结构和正则表达式非常重要(这里的解决方法就分别用到了),虽然平时用得少,到一道有应用场景,你就会发现数据结构和正则表达式的强大了。

相关标签: JS括号匹配问题