JS bracket matching problem

I did a bracket matching question on codewars.

Question

To determine whether the three brackets {}, [], and () in a string match, you need to consider the nesting situation.

Example:

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

Solution

There are only two basic situations for this problem. One is parallel, that is, there is no nesting, such as ()[]{}; the other is nesting. ,like{[()]}. The first situation is relatively simple, and the second situation is more difficult. The solution to the problem of nesting is to first match the innermost bracket pair, which is what we often say starts from the inside.

The first method:

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

In this method, find pairs of brackets, and then replace pairs of adjacent brackets with empty strings, that is, delete them. Finally, determine whether the length of the string is 0. If yes, it means a complete match, otherwise, it means a smaller match.
In fact, this kind of plan is a typical "disintegration from the inside". Let's take {[()]} as an example. If you observe, now only the innermost () is paired and adjacent. When () is replaced with an empty string, [] becomes paired and adjacent. adjacent, and then replace it with an empty string. The search continues in this loop until no more pairs of adjacent parentheses are found.

The second method:

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
}

This method is to store the left half bracket, that is, (, [, {, {, etc.) into the stack. When the right half bracket, that is, ), ], } is traversed, the stack is executed. Pop the stack operation, and then match the popped left half bracket with the traversed half bracket to see if it is the matching other half bracket. If the traversal is completed, the length of the stack is judged. If it is 0, it matches, otherwise, it matches.
We also take {[()]} as an example. The first three items, namely {, [, (are pushed into the stack, when traversing to), the '(' on the top of the stack is popped out and compared with ) to see if they match. . The following ] and } are the same.

Conclusion

Now I gradually find that data structures and regular expressions are very important (the solutions here are used separately). Although they are rarely used in daily life, when there are application scenarios together, you will find that data structures and regular expressions are 's powerful.