Die Umwandlung eines infix-Ausdrucks (mit den Klammern) in einem binären Baum

Als Teil einer Java-Zuordnung, ich habe eine Eingabe arithmetischer Ausdruck und speichern Sie Sie in einem binären Baum.

Ich habe alles getan, was notwendig für die Zuordnung außer für den Teil, wo ich das gelesen habe in der Zeichenfolge des Ausdrucks, und speichern Sie es in den binären Baum.

Habe ich eine Klasse " BinaryTree. Seine einzige Feld ist ein treenode-Objekt mit dem Namen root. Das treenode-Objekt ist definiert als eine innerclass in BinaryTree. Es hat 3 Felder, ein generisches Daten-Feld, und zwei Kinder (Links und rechts), die Typ BinaryTree.

Ich habe eine sehr schwierige Zeit definiert einen Algorithmus für das Lesen in einem Ausdruck wie

(5*(2+3)^3)/2

und speichern es in einem Baum wie diese

             /
        ^          2
    *       3
  5   +
     2  3

Kann jemand helfen mit dem Algorithmus?

  • Versuchen Sie eine einfache Gleichung string first: 1+2. Wenn du das nicht: 1+2*3. Noch komplexer: 1*2+3. Schließlich: (1+2)*3
  • Wollen Sie eine Erklärung für den algo?
InformationsquelleAutor HesNotTheStig | 2012-04-24
  1. 6

    Werfen Sie einen Blick auf die Rangier-yard-Algorithmus. Aus Wikipedia:

    In computer science, Rangier-yard-Algorithmus ist eine Methode für das analysieren von mathematischen Ausdrücken angegeben in infix-notation. Es kann verwendet werden, um eine Ausgabe in Umgekehrter polnischer notation (RPN) oder als abstract syntax tree (AST). Der Algorithmus wurde erfunden von Edsger Dijkstra und mit dem Namen der "Verschiebebahnhof" Algorithmus, da seine Funktionsweise ähnelt der einer Rangierbahnhof. Dijkstra erstmals beschrieben, der Rangierbahnhof Algorithmus Mathematisch Centrum Bericht HERR 34/61.

    InformationsquelleAutor NPE
  2. 3

    Hier einige C++ - code zu erstellen, ein binärer Ausdruck Baum verwendet zwei stacks, einen für den Betreiber und eine für die Operanden. Schließlich enthält der Operanden stack ein element, der vollständigen binären Ausdruck Baum.

    InformationsquelleAutor Kurt Krueckeberg
Schreibe einen Kommentar