JS-Klammer-Matching-Problem

Ich habe eine Klammer-Matching-Frage zu Codewars gestellt.

Frage

Um festzustellen, ob die drei Klammern {}, [] und () in einer Zeichenfolge übereinstimmen, müssen Sie die Verschachtelungssituation berücksichtigen.

Beispiel:

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

Lösung

Es gibt nur zwei grundlegende Situationen dieses Problems, eine ist parallel, das heißt, es gibt keine Verschachtelung, wie zum Beispiel () []{}; Eine andere Situation ist eine verschachtelte Situation, wie zum Beispiel {[()]}. Die erste Situation ist relativ einfach und die zweite Situation ist schwieriger. Die Lösung des Verschachtelungsproblems besteht darin, zunächst das innerste Klammerpaar abzugleichen, was wir oft als „von innen“ bezeichnen.

Die erste Methode:

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

Bei dieser Methode werden Klammerpaare gesucht und dann Paare benachbarter Klammern durch leere Zeichenfolgen ersetzt, d. h. gelöscht. Bestimmen Sie abschließend, ob die Länge der Zeichenfolge 0 ist. Ja, es bedeutet eine vollständige Übereinstimmung, andernfalls bedeutet es eine kleinere Übereinstimmung.
Tatsächlich handelt es sich bei einem solchen Plan um einen typischen „Zerfall von innen“. Nehmen wir als Beispiel {[()]}, wenn Sie beobachten, dass nur die innerste () durch eine leere Zeichenfolge ersetzt wird und diese dann ersetzt wird mit einer leeren Zeichenfolge. Die Suche wird in dieser Schleife fortgesetzt, bis keine Paare benachbarter Klammern mehr gefunden werden.

Die zweite Methode:

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
}

Diese Methode besteht darin, die linke halbe Klammer, also (, [, { usw.) in der rechten halben Klammer zu speichern durchlaufen wird, d. h. ), ], }, führt der Stapel eine Pop-Operation aus und vergleicht dann die gepoppte linke halbe Klammer mit der durchquerten halben Klammer, um zu sehen, ob es sich um die passende andere halbe Klammer handelt. Wenn die Durchquerung abgeschlossen ist, wird die Länge des Stapels beurteilt. Wenn sie 0 ist, stimmt sie überein, andernfalls stimmt sie überein.
Wir nehmen auch {[()]} als Beispiel, nämlich {, [, (in den Stapel geschoben, beim Durchlaufen zu) werden mit dem '(' oben auf dem Stapel verglichen nachdem es aus dem Stapel genommen wurde. Sehen Sie, ob es übereinstimmt. Die folgenden ] und } sind gleich.

Fazit

Jetzt stelle ich nach und nach fest, dass Datenstrukturen und reguläre Ausdrücke sehr wichtig sind (die Lösungen hier werden separat verwendet, obwohl sie im täglichen Leben selten verwendet werden, wenn es Anwendungsszenarien zusammen gibt). , Sie werden die Leistungsfähigkeit von Datenstrukturen und regulären Ausdrücken entdecken.