Hier könnt Ihr gute, von Euch geschriebene Codes posten. Sie müssen auf jeden Fall funktionieren und sollten möglichst effizient, elegant und beispielhaft oder einfach nur cool sein.
DarkDragon hat geschrieben:
Aber da würde der AVL Baum die Prioritäten der Operationen durcheinanderbringen und eventuell wären dann Operatoren plötzlich Blattknoten was nicht sein kann bei Infix. Immerhin geht der Parser/Interpreter dann durch den Baum durch und Rechnet bei einem "+" Knoten dann LinkerTeilbaum + RechterTeilbaum.
OK, ehrlich gesagt verstehe ich jetzt immer noch nicht den Unterschied zwischen einem AVL-Baum und dem
Syntaxbaum, den ich verwendet habe. Die Operatoren sind in meinem Fall Knoten, die maximal zwei weitere
Unterknoten besitzen können, die genau eine Ebene darunter liegen...
Der Syntaxbaum wird nicht balanciert. Wenn du einen neuen Knoten in den AVL Baum einfügst, dann prüfst du bis zur Wurzel ob ein Knoten unbalanciert ist. Wenn ja rotiere ihn damit der Knoten wieder balanciert ist. D.h. angenommen du hast einen Syntaxbaum der so aussieht:
Dann wäre der Ausdruck nichtmehr a + c * (d + e) sondern (a + c) * (d + e) und entspräche etwas ganz anderem.
Ein Ausdrucksbaum ist auch nicht nur in Binärbaum. Nehmen wir einmal an du hast einen Funktionsaufruf in deinem Ausdruck, dann hast du einen Baum mit mehr als 2 Nachfolgern:
testfkt(a, b, c, d)
Angenommen es gäbe einen Algorithmus mit imaginärer Laufzeit O(i * n), dann gilt O((i * n)^2) = O(-1 * n^2) d.h. wenn man diesen Algorithmus verschachtelt ist er fertig, bevor er angefangen hat.
Danke für die ausführliche Erklärung. Jetzt verstehe ich auch, wieso ein AVL-Baum so viel Arbeit bedeutet.
Nur so am Rande: Das mit den mehreren Parametern für Funktionsaufrufe löst man gerne durch einen Stack, der duch aufeinanderfolgende "Push"-Nodes (Ein Knoten mit einem Unterknoten (der Parameter)) gefüllt wird. D.h. zur Ausführung braucht man im Prinzip wirklich nur maximal zwei child nodes.
"Wahrlich es ist nicht das Wissen, sondern das Lernen, nicht das Besitzen sondern das Erwerben, nicht das Dasein, sondern das Hinkommen, was den grössten Genuss gewährt." - Carl Friedrich Gauß
Josef Sniatecki hat geschrieben:Nur so am Rande: Das mit den mehreren Parametern für Funktionsaufrufe löst man gerne durch einen Stack, der duch aufeinanderfolgende "Push"-Nodes (Ein Knoten mit einem Unterknoten (der Parameter)) gefüllt wird. D.h. zur Ausführung braucht man im Prinzip wirklich nur maximal zwei child nodes.
Das löst dann aber der Kompiler. Ein Ausdrucksbaum wird aber davor benötigt. Der Baum wird dann optimiert vom Compiler und jeder Knoten hat sozusagen eine Methode "compile" dann wird der Code generiert (von einem bestimmten Knoten inklusive seiner Kinder). Vielleicht übersetze ich meinen Matheparser mal, das könnte man leicht verändern und man hätte schon einen richtigen Kompiler für eine Programmiersprache.
Angenommen es gäbe einen Algorithmus mit imaginärer Laufzeit O(i * n), dann gilt O((i * n)^2) = O(-1 * n^2) d.h. wenn man diesen Algorithmus verschachtelt ist er fertig, bevor er angefangen hat.
