[Erledigt] Suche Parser - Tutorial

[mytar]

Ja ich verstehe.

@torud: Bei wikipedia hab ich schon geschaut.

Wie erzeuge ich aus so einem Ausdruck einen Termbaum?

greetz
mytar

[xineohp]

moin,

du suchst den rangniedrigsten Operator in deinem Term (und zwar nur in der äußersten Klammerebene, d.h. Ausdrücke in Klammern werden ignoriert):
also zB: 1-2*(3+4) --> niedrigster Operator: "-"

Diesen trägst du dann als Wurzel in deinen Baum ein. Anschließend rufst du deine Funktion rekursiv wieder auf, und zwar einmal mit dem linken und einmal mit dem rechten Teilausdruck:
also nachdem obigen Beispiel:

linker Teil: 5 --> kein Operator vorhanden, 5 wird als linker Nachfolger der Baumwurzel("-") eingetragen.

rechter Teil: 2*(3+4) --> liefert "*" als niedrigsten Operator, dieser wird als rechter Nachfolger der Baumwurzel("-") eingetragen.
Anschließend: erneute Rekursion mit 2 und (3+4):

linker Teil: 2 -->kein Operator vorhanden, 2 wird als linker Nachfolger des Knotens("*") eingetragen.

rechter Teil: (3+4) --> kein Operator (außerhalb der Klammern; s.o.) vorhanden UND 1.Zeichen = "(" es folgt: der gesamte Ausdruck ist von Klammern umschlossen. daher: erstes und letztes Zeichen löschen --> 3+4 und wieder Rekursion --> niedrigster (und einzigster Operator) = "+" ... als Knoten eintragen ... Rekursion linker Teil: 3 ; Rekursion rechter Teil: 4

so, Baum fertig

Code:

  1-2*(3+4) -->

     -
    / \
   1   *
      / \
     2   +
        / \
       3   4

[mytar]

Ich verstehe jetzt langsam.

Die Rekursionsaufrufe sind genau wie bei Quicksort.

greetz
mytar