JS ブラケット マッチングの問題

codewars でブラケット マッチングの質問をしました。

質問

文字列内の 3 つの括弧 {}、[]、および () が一致するかどうかを判断するには、入れ子の状況を考慮する必要があります。

例:

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

解決策

この問題には 2 つの基本的な状況しかありません。1 つは ()[]{} のような入れ子ではなく、もう 1 つは入れ子です。 ()]}。最初の状況は比較的単純ですが、2 番目の状況はより困難です。ネストの問題の解決策は、最初に最も内側のブラケットのペアを一致させることです。これは、内側から始めるとよく言われることです。

最初の方法:

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

このメソッドでは、括弧のペアを検索し、隣接する括弧のペアを空の文字列に置き換えます (つまり、削除します)。最後に、文字列の長さが 0 かどうかを判断します。 「はい」の場合は完全一致を意味し、そうでない場合はより小さい一致を意味します。
実際、この種の計画は典型的な「内部からの崩壊」です。 {[()]} を例に挙げると、最も内側の () だけがペアになって隣接しています。() が空の文字列に置き換えられると、[] がペアになって隣接します。空の文字列を使用します。隣接する括弧のペアが見つからなくなるまで、このループで検索が続けられます。

2番目のメソッド:

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
}

このメソッドは、左半分の括弧、つまり(、[、{、{など)をスタックに格納し、右半分の括弧、つまり)、]、を格納します。 } が走査されると、スタックが実行されます。スタック操作をポップし、ポップされた左半括弧と走査された半括弧を照合して、それが一致するもう一方の半括弧であるかどうかを確認します。トラバースが完了していればスタックの長さを判定し、0であれば一致、そうでなければ一致します。
また、例として {[()]} を取り上げます。最初の 3 つの項目、つまり {、[、 (スタックに移動するときにプッシュされる) は、スタックの先頭にある '(' と比較されます。スタックから取り出したものと ) が一致するかどうかを確認します。以下の]と}は同じものです。

結論

ここで、データ構造と正規表現が非常に重要であることが徐々にわかりました (ここでのソリューションは個別に使用されます)。これらは日常生活ではめったに使用されませんが、アプリケーションのシナリオが一緒になると、データ構造と正規表現が重要であることがわかります。正規表現は強力です。