在上做了一道括号匹配的题目。

题目

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

例子：

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，则匹配，否则，比匹配。我们同样以{[()]}为例，前三项，即{

、[、(入栈，当遍历到)的时候，位于栈顶的'('后出栈与)比较，看是否匹配。后面的]、}也是一样道理。

结语

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