[Mathe/Informatik]Verschachtelung von Termen "aufloesen"

[ShadowMan]

Da muss ich squeaker leider recht geben. Haben sowas an der Uni auch immer mit Bäumen gemacht. Alternative dazu sind Listen.

Womit willst du das eigentlich programmieren?

Lieben Gruß,
Manuel ;-]

 

[Surma]

@Shadow: Java
@squeaker: polnische Notation? (hoert sich sehr... geklaut an , von ungarischer Notation )

 

[squeaker]

du könntest recht haben, könnte auch ungarisch gewesen sein. Halt das was die HP-Rechner sprechen.

z.B. 2+3 entspricht 2 3 +

damit ergibt sich für 5*5+2 -> 5 5 * 2 +
und für (5+5)*2 5 5 + 2 *

man spart sich also alle Klammern. Und kann relativ einfach auf einem Stack rechnen ohne den ganzen String vorher geparst zu haben.

 

[Surma]

Hmm... das hoert sich sehr gut an! Werd mich mal erkundigen!

PS: Um vor Verwirrung zu bewahren, es definitv nicht die ungarische Notation. Diese Notation "schreibt vor" vor Variablen-Namen imemr zu schreiben ob Point,, global, welcher Datentyp etc. (zB g_piNamelength (global, pointer, int, "Namelength")

Thx

 

[squeaker]

hier ein link dazu - wenn auch leicht OT

reversed polish notation

 

[Grimreaper]

OT: Diese Notation wird auch Postfix-Notation gennant (Alternativen: Präfix und Infix).

mfg Grimreaper

 

[ShadowMan]

Und das Ganze nennt man traversieren bzw. die Traversierungsart....

...um den OT zu komplettieren *gg*

Gruß,
Manuel ;-]

 

[Surma]

wieso soll das alles OT sein? das sind mir alles grosse Hilfen auf das Thema bezogen. (Das war OT)

Aber als ich gestern noch bis 3h wach lag und alle moeglichen Probleme des Parser auf Papiergeloest habe, ist mir aufgefallen, das so ein Tree-Parser anscheinend doch der unkomplizierteste und leicht verstehbarere ist.
Ich muss nur noch schauen, wie ich das Ding idiotensicher mache.
z.B (((4+2)))*3 das er da nicht ein Fehler macht
oder wen bestimmte ihre Verknuepfung nicht direkt untersich sonderen mehrere Ebenen untersich haben.
z.B (2*3)*4-2*4*(4+3)-(2*3)

wenn er feritg ist, poste ich den Code hier einfach mal (Link natuerlich )

 

[squeaker]

Schau mal in einer Bibliothek deiner Wahl nach Rober Sedgewick "Algorithmen in C++" bzw. Java was auch immer. Da gibt's ein kurzes Kapitel zu dem Thema (Kapitel 21 - Parsing).

Viel Spass

 

[Tobias Menzel]

(((4+2)))*3

sollte eigentlich kein Problem sein: bei einem rekursiven Aufruf hast du:

(4+2)
6
((6))
(6)
6

passt auch.
auch

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

lässt sich genau so behandeln. Da die Klammern nicht nur rekursiv aufgerufen werden, sondern eben auch der reihe nach, kein Problem. Aufpassen musst Du nur nach dem Auflösen, dass die Punktrechnung vor der Strichrechnung drankommt. Geh den Term operatorweise durch und berechne zuerst die Unterterme mit den höchsten Prioritäten.

Gruß

P.S.: ich plane grade, mein damaliges Programm von VB auf C++ zu portieren... aber ich nehme mal an, Du wirst eher als ich fertig sein