JS括号匹配问题

lordharrd 发布于2019-08-20 11:38 / 1032人阅读

摘要：在上做了一道括号匹配的题目。题目判断字符串中的三种括号是否匹配，需要考虑嵌套的情况。是，则表示完全匹配，否则，比匹配。

在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，则匹配，否则，比匹配。
我们同样以{[()]}为例，前三项，即{、[、(入栈，当遍历到)的时候，位于栈顶的"("后出栈与)比较，看是否匹配。后面的]、}也是一样道理。

结语

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

云服务器 GPU云服务器 java匹配括号里的二括号匹配c语言 php版本匹配问题稳定匹配问题c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/80675.html

JS正则表达式一条龙讲解，从原理和语法到JS正则、ES6正则扩展，最后再到正则实践思路

摘要：控制权和传动这两个词可能在搜一些博文或者资料的时候会遇到，这里做一个解释先控制权是指哪一个正则子表达式可能为一个普通字符元字符或元字符序列组成在匹配字符串，那么控制权就在哪。温馨提示：文章很长很长，保持耐心，必要时可以跳着看，当然用来查也是不错的。正则啊，就像一座灯塔，当你在字符串的海洋不知所措的时候，总能给你一点思路；正则啊，就像一台验钞机，在你不知道用户提交的钞票真假的时候，...

Michael_Lin 2019-08-20 13:39 评论0 收藏0
正则之基本入门

摘要：忽略大小写全文查找出现的所有匹配字符多行查找全文查找忽略大小写所以使用之后可以这样写表示忽略大小写匹配或者正式入门正则正则其实就是用来匹配字符串的。惰性量词使用方法基本量词该量词和贪婪量词就像，一个是消极怠工，一个是积极工作。以前看了许许多多的正则教程，收货并不多，往往都是蜻蜓点水，一点就过。事实上，正则用处真的超级大，比如匹配innerHTML的内容，以及表单验证，也是非他莫属。这...

ormsf 2019-08-19 17:31 评论0 收藏0
读《精通正则表达式》-- 网上 js 正则基础教程没有涉及的一些知识

摘要：正则起源最近看完了精通正则表达式，收获颇丰，略过了一些晦涩难懂的理论部分，主要看了实战和教程部分。然后下面说一下以上两个基础教程里没说到的知识点。最后以上是我在精通正则表达式一书中得到的一些收获，希望能分享给大家，如有错误欢迎指正。正则起源最近看完了《精通正则表达式》，收获颇丰，略过了一些晦涩难懂的理论部分，主要看了实战和教程部分。下面引用一下百度百科里的内容。正则表达式的鼻...

GT 2019-08-23 10:42 评论0 收藏0
JS正则表达式元字符

摘要：表示非单词字符，等效于正则教程返回完整的字符串，因为，中文算作是非单词字符。行首行尾，修饰符形式修饰符的作用是修改和在正则表达式中的作用，让它们分别表示行首和行尾。正则描述正则描述 f 匹配换页符匹配制表符匹配换行符 v 匹配垂直制表符匹配回车 s 匹配单个空格，等同于[f v]; S...

CODING 2019-08-22 10:55 评论0 收藏0
正则表达式

摘要：正则表达式产生回溯的地方贪婪量词前面的匹配的是，后面的匹配的是惰性量词惰查看原文站点，更多扩展内容及更佳阅读体验！查看原文：正则表达式正则表达式正则表达式是匹配模式，要么匹配字符，要么匹配位置。字符匹配两种模糊匹配正则表达式能实现模糊匹配模糊匹配，有两个方向上的模糊：横向和纵向横向模糊匹配横向模糊指的是，一个正则可匹配的字符串的长度不是固定的实现方式是使用...

Dean 2019-08-22 18:09 评论0 收藏0