Binäre Bäume und Taschenrechner

Hallo,

ich soll einen Taschenrechner auf DOS-Ebene basteln, wobei ich als Lösung binäre Bäume oder arithmetische Bäume benutzen muß.Der User soll in der DOS- Umgebung z.B. an einem Stück 3+4 eingeben können.
Ich bin am überlegen und verzweifel bald weil ich nicht drauf komme wie ich das umsetzen könnte.Hat jemand vielleicht einen kleinen Tip für mich?
vielen Dank schon mal...

C++ Forumbot

Dieser Thread wurde von Moderator/in Jansen aus dem Forum Borland C++ Builder (VCL/CLX) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

*grimmsen**

Zunächst musst du dir einen Baum implementieren. Welche Programmiersprache solls denn sein? 3+4 ist ja noch noch das komplizierte 3+4*1 ist das was die Sache nichttrivial macht.
Hast du deinen Baum aus der Formel erstellt musst du Ihn mit einem Algorithmus durchwandern. Such mal nach dem Stichwort Traversierung. Für solche Fälle greift aber Inorder- oder Postorder-Traversierung ???
Ist zu lange her!

Danke erstmal.Aslo das ganze soll in C geschrieben werden.und du hast schon recht,es soll später 3+4*1 eingeben werden oder auch sowas 3*(4-2)+6
Ich werde mal nach deinem Begriff suchen,vielleicht finde ich was. Glaub so verzweifelt war ich noch nie.An solchen Tagen zweifel ich immer daran überhaupt für die Programmierung geschaffen zu sein

SirLant

Den Parser kannst du als "Parser für rekursiven Abstieg" implementieren, wenn ihr
so eine Aufgabe aufbekommen habt, habt ihr so etwas aber sicher bereits durchgenommen
oder?

Das ganze musst du dann halt vor dem parsen in nen bin baum packen und danach den
parser drüberlaufen lassen. Habe selber noch nie nen Parser auf nem Baum gebastelt.
Kann dir daher keine konkreten Tipps geben.

Jester

Hm, ich würd eher sagen: Der Parser baut den Baum. Danach isses ja einfach. Man muß ja nurnoch den Baum auswerten.

Ich würd's so aufbauen:

Eine Tree-Node bauen als Basisklasse. Die bekomme eine Methode evaluate.
Dann bauen wir verschiedene andere Nodes, zum Beispiel eine NumberNode, die gibt mit evaluate einfach ihre Zahl zurück. Dann baust Du eine SumNode, die bekommt zwei Zeiger, einen auf Summand1, einen auf Summand2. evaluate liefert bei dieser Node: evaluate(Summand1) + evaluate(Summand2), -,*,/ analog.

Jetzt muß man versuchen beim parsen des Ausdrucks den Baum korrekt aufzubauen. Ist das geschafft genügt ein einfaches evaluate auf die Wurzel des Baumes und der komplette Ausdruck ist ausgewertet.

MfG Jester

ethereal

Falls jemand in deinem Bekanntenkreis den Stroustrup hat: da is auch ne Implementierung von einem Taschenrechner drin (Kap.6), allerdings noch ohne Bäume. Dennoch ein schönes Beispiel für rekursiven Abstieg...
Gruß
E-the-Real

TDKBacke

Zum Aufbau des Baumes: Suche in diesem pdf einmal nach "Strukturbäume arithmetischer Ausdrücke"(Seite 67ff müsste das sein, sind insgesamt vier Folien).
Ist eigentlich recht einfach:
Abgegriffen wird von links nach rechts. Bei gleicher Hierarchie des neuen und alten Operators wird der bisherige Baum zum linken Nachfolger des neuen Operatorknotens, auf den künftig die Wurzel zeigt. Bei höherer Priorität des neuen Operators wird der neue Baumabschnitt rechter Nachfolger des Operatorknotens, auf den der Wurzelzeiger deutet. Ausdrücke in Klammern müssen als eigenständige Bäume behandelt und dann eingehängt werden.
(Wobei ich das bisher nur auf dem Papier machen musste. In der Praxis - z.B. bei Interpretern - nimmt man gerne den Operator-/Operand-Stack (auf der nächsten Folie), der ist sowohl in der Entwicklung als auch in Ausführung schneller.)

Danke für die vielen Rückmeldungen *euch mal alle drück*
Wir haben leider noch keine Klassen oder generell objektorientiertes durchgenommen,alles was drankam war innerhalb von 90 Minuten eine Übersicht über Listen,doppelt verkette Ringe und Bäume und dann hieß es macht nen Taschenrechner mit binären Bäumen inklusive Präsentation und ne Quelle zu doppelt verketteten Ringen mit Sortierung.
Naja,auf jeden Fall werd ich mir eure Tipps genau ansehen und versuchen es so umzusetzen wie ihr gesagt habt. Danke nochmal!

huhu,

also da bin ich wieder. ich hab meinen quelltext jetzt fertig alles in ansi c. ich hab bloß ein problem: rechenzeichen ( wie plus minus mal geteilt usw) werden links im baum gespeichert,zahlen rechts. die wurzel ist gleich der ersten eingeben zahl. gibt es eine möglichkeit die wurzel zu verschieben?ich muß es so machen,dass die wurzel aus einem rechenzeichen besteht.
mein algo sieht so aus: Rechenoperatioren = innere Knoten und die zahlen sollen die blätter sein. wurzel wäre dann das mal zeichen oder geteilt,je nach dem was eingegeben wurde.das würde erstmal so reichen. bloß wie kann ich das umsetzten?habt ihr vielleicht noch einmal tipps für mich?