Analysieren eines booleschen Ausdrucks

1106. Einen booleschen Ausdruck analysieren

Schwierigkeit:Schwer

Themen:String, Stack, Rekursion

Ein boolescher Ausdruck ist ein Ausdruck, der entweder wahr oder falsch ergibt. Es kann eine der folgenden Formen haben:

• 't', das als wahr ausgewertet wird.
• 'f', das als falsch ausgewertet wird.
• '!(subExpr)', das das logische NICHT des inneren Ausdrucks subExpr.
ergibt
• '&(subExpr₁, subExpr₂, ..., subExpr_n)', das als das logische UND des Inneren ausgewertet wird Ausdrücke subExpr₁, subExpr₂, ..., subExpr_n wobei n >= 1.
• '|(subExpr₁, subExpr₂, ..., subExpr_n)', das das logische ODER des Inneren ergibt Ausdrücke subExpr₁, subExpr₂, ..., subExpr_n wobei n >= 1.

Angenommen ein Zeichenfolgenausdruck, der einen booleschen Ausdruck darstellt, wird die Auswertung dieses Ausdrucks zurückgegeben.

Es ist garantiert, dass der angegebene Ausdruck gültig ist und den angegebenen Regeln folgt.

Beispiel 1:

• Eingabe: Ausdruck = "&(|(f))"
• Ausgabe:false
• Erklärung:
  • Bewerten Sie zunächst |(f) --> F. Der Ausdruck lautet jetzt „&(f)“.
  • Bewerten Sie dann &(f) --> F. Der Ausdruck lautet jetzt „f“.
  • Zum Schluss geben Sie false zurück.

Beispiel 2:

• Eingabe: expression = "|(f,f,f,t)"
• Ausgabe:wahr
• Erklärung: Die Auswertung von (falsch ODER falsch ODER falsch ODER wahr) ist wahr.

Beispiel 3:

• Eingabe: expression = "!(&(f,t))"
• Ausgabe:wahr
• Erklärung:
  • Bewerten Sie zunächst &(f,t) --> (falsch UND wahr) --> falsch --> F. Der Ausdruck lautet jetzt „!(f)“.
  • Dann bewerten Sie !(f) --> NICHT falsch –> WAHR. Wir geben true zurück.

Einschränkungen:

• 1 <= expression.length <= 2 * 10⁴
• Ausdruck[i] ist eines der folgenden Zeichen: '(', ')', '&', '|', '!', 't', 'f' und ','.

Hinweis:

1. Schreiben Sie eine Funktion „parse“, die die Hilfsfunktionen „parse_or“, „parse_and“, „parse_not“ aufruft.

Lösung:

Wir werden die Lösung in kleinere Funktionen aufteilen, die das Parsen und Auswerten verschiedener Arten von Ausdrücken übernehmen: parse_or, parse_and, parse_not, und eine Hauptparse-Funktion, die das Parsen des Ausdrucks rekursiv übernimmt. Wir werden einen Stapel verwenden, um verschachtelte Ausdrücke zu verfolgen und sie Schritt für Schritt auszuwerten.

Ansatz:

1. Parsing und Rekursion:

   • Verwenden Sie einen Stapel, um den Überblick über Ausdrücke zu behalten, wenn Sie auf verschachtelte Klammern stoßen.
   • Zeichen nacheinander verarbeiten und den Stapel für verschachtelte Auswertungen verwalten.
   • Wenn Sie auf eine schließende Klammer stoßen, extrahieren Sie den letzten Satz von Ausdrücken und wenden Sie die logische Operation an (&, | oder !).

2. Hilfsfunktionen:

   • parse_or: Wertet |(expr1, expr2, ..., exprN) aus, indem es „true“ zurückgibt, wenn mindestens ein Unterausdruck wahr ist.
   • parse_and: Wertet &(expr1, expr2, ..., exprN) aus, indem nur dann „true“ zurückgegeben wird, wenn alle Unterausdrücke wahr sind.
   • parse_not: Wertet !(expr) aus, indem das Gegenteil des Unterausdrucks zurückgegeben wird.

3. Ausdrucksbehandlung:

   • Einzelne Zeichen wie t und f werden direkt in wahr und falsch übersetzt.
   • Wenn eine Operation auftritt (&, |, !), werden die inneren Ausdrücke basierend auf ihren jeweiligen Regeln ausgewertet.

Lassen Sie uns diese Lösung in PHP implementieren: 1106. Einen booleschen Ausdruck analysieren

  
  
  Erläuterung:




Hauptfunktion (parseBooleanExpression):


Durchläuft den Ausdruck und verschiebt Zeichen auf einen Stapel.
Wenn a auftritt, werden alle Elemente in den Klammern gesammelt und anhand der Operation (&, |, !) ausgewertet.
Konvertiert Ergebnisse in „t“ (wahr) oder „f“ (falsch) und legt sie zurück auf den Stapel.







Hilfsfunktionen:



parse_and: Gibt true zurück, wenn alle Unterausdrücke „t“ (true) sind.

parse_or: Gibt true zurück, wenn ein Unterausdruck „t“ ist.

parse_not: Kehrt den booleschen Wert eines einzelnen Unterausdrucks um.








  
  
  Beispielhafte Vorgehensweise:




Eingabe: „&(|(f))“


Stapelverarbeitung:



&, (, |, (, f, ), ) → Der innere Ausdruck |(f) wird zu f ausgewertet.
Ergibt &(f), was zu f ausgewertet wird.


Ausgabe: false.



Eingabe: „|(f,f,f,t)“


Bewertet das | Betrieb:


Findet ein „t“ und wertet es daher als wahr aus.


Ausgabe: wahr.



Eingabe: „!(&(f,t))“

Stapelverarbeitung:



!, (, &, (, f, ,, t, ), ) → &(f,t) ergibt f.

!(f) wird dann als wahr ausgewertet.


Ausgabe: wahr.





  
  
  Komplexität:




Zeitkomplexität: O(N), wobei N die Länge des Ausdrucks ist. Jedes Zeichen wird eine begrenzte Anzahl von Malen verarbeitet.

Raumkomplexität: O(N), aufgrund des Stapels, der zum Verfolgen verschachtelter Ausdrücke verwendet wird.


Diese Lösung eignet sich gut für die Einschränkungen und sollte die Eingabegröße effektiv bewältigen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonAnalysieren eines booleschen Ausdrucks. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!