Wie kann ich in Java einen Baum aus einem arithmetischen Ausdruck analysieren und erstellen?

Analysieren eines arithmetischen Ausdrucks und Erstellen eines Baums daraus in Java

Dieser Artikel befasst sich mit der Aufgabe, einen arithmetischen Ausdruck zu analysieren und einen zu konstruieren entsprechende Baumdatenstruktur in Java. Das Ziel besteht darin, einen Ausdruck wie „(5 2)*7“ in einen Baum zu verarbeiten, der der Struktur des Ausdrucks ähnelt.

Ansatz: Verwenden eines Stapels

Um das zu analysieren Ausdruck kann ein Stapel verwendet werden. Der Ansatz beinhaltet die iterative Verarbeitung von Token aus dem Ausdruck:

• Wenn eine öffnende Klammer „(“ angetroffen wird, wird sie auf den Stapel verschoben.
• Wenn eine Zahl (Operand) angetroffen wird , wird er als Blattknoten gespeichert und auf den Stapel verschoben.

• Wenn ein Operator ( , -, *, /) angetroffen wird:

  • Seine Priorität wird verglichen zum obersten Operator auf dem Stapel.
  • Wenn die Priorität niedriger oder gleich ist, wird der Ausdruck bis zum vorherigen „(“ oder dem Anfang des Ausdrucks ausgewertet.
  • Das Ergebnis von Die Auswertung wird auf den Stapel verschoben.

Beispiel: Parsen von „(5 2)*7“

Erwägen Sie das Parsen des Ausdrucks „ (5 2)*7":

• "(" wird auf den Stapel geschoben.
• "5" wird als Blattknoten auf den Stapel geschoben.
• " " wird auf den Stapel geschoben.
• "2" wird als Blattknoten auf den Stapel geschoben.

• )" wird angetroffen, also der Ausdruck "5 2" wird ausgewertet:

  • Die Blattknoten „5“ und „2“ werden vom Stapel entfernt.
  • Ein neuer Zusatzknoten „ “ wird erstellt, mit den beiden Blattknoten als dessen Kinder.
  • Der Additionsknoten wird auf den Stapel geschoben.
• "*" wird auf den Stapel geschoben.
• "7" wird auf den Stapel geschoben der Stapel als Blattknoten.

• "eof" (Ende des Ausdrucks) wird angetroffen, daher wird der Ausdruck "(Knoten) 7" ausgewertet:

  • Der Multiplikationsknoten „(*node)“ und der Blattknoten „7“ werden vom Stapel entfernt.
  • Ein neuer Multiplikationsknoten „*“ wird erstellt und auf den Stapel verschoben.

Die endgültige Baumstruktur, die vom Stapel abgerufen wird, stimmt mit dem ursprünglichen Ausdruck überein:

    *
   / \
  +   7
 / \
5   2

Schlussfolgerung

Verwendung Ein Stapel zum Parsen arithmetischer Ausdrücke ermöglicht die effiziente Erstellung von Baumdatenstrukturen, die diese Ausdrücke darstellen. Dieser Ansatz ermöglicht die Durchführung weiterer Operationen und Analysen an den analysierten Bäumen.

Das obige ist der detaillierte Inhalt vonWie kann ich in Java einen Baum aus einem arithmetischen Ausdruck analysieren und erstellen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!