Hallo!

Nun also doch nicht in der Sb sondern als Thema:

Also, wir haben als Aufgabe bekommen, einen MatheParser zu schreiben, welcher seine Eingabe als polnische Notation bekommt.
Mein Kollege ist sich auch ganz sicher, dass es nicht die UPN ist, denn die wäre ja eigentlich sinnvoller. (Es ging ja darum, das Problem zu vereinfachen, jetzt erschwert es das ganze eher).

Intern möchte ich schon ganz gerne mit UPN arbeiten (macht sich ja auch viel besser) und muss daher jetzt PN zu UPN umstellen.

Jedoch hab ich noch nicht ganz den Durchblick, wie die PN eigentlich aussieht.

Deswegen hier einfach mal ein Beispiel:

Normal: 1+5*7+68*9*2
UPN: 5 7 * 68 9 * 2 * + 1 +
PN: ??

Ich hoffe ihr könnt mir da helfen, Teekeks

Gut, hier ist doch etwas mehr Platz als in der Shoutbox.

Das ist bei mir zwar schon ein paar Jahre her, aber das sollte kein Problem sein hoffe ich.
Das Prinzip ist dir sicher klar: Die Operatoren kommen jeweils vor die Operanden (daher bei der UPN entsprechend nach hinten).

In deinem Beispiel hast du eine Addition aus einer Zahl und zwei Produkten. Addiert werden also:Davor kommen wiederum die Operatoren für die Additionen. Das ganze sieht dann also so aus:

Teekeks hat folgendes geschrieben :

UPN: 5 7 * 68 9 * 2 * + 1 +

Ich denke es geht auch beides, aber ich hätte das so geschrieben: Jedenfalls finde ich mit höheren Programmiersprachen umgekehrt die polnische Notation leichter zu implementieren.

Und wie Interpretiere ich dann diese Polnische Notation?

Bei der Umgekerten polnischen Notation muss man ja jeweis immer nur alle zahlen auf nen FiLo-Stack packen und bei operatoren die entsprechende Anzahl an zahlen vom stack holen und das Ergebnis wieder auf den Stack werfen.

Beim anderen hab ich keine Ahnung wie ich da ran gehen soll.

Aber schon mal danke für deinen Post!

Edit: man könnte ja auch einfach nur das ganze von Hinten nach vorne interpretieren, dann scheint es das selbe wie die UPN zu sein.

Ich würde eine Baumstruktur verwenden und das ganze auslesen und dann auswerten. Das kann man rekursiv mit einem PChar als Zeiger auf die aktuelle Stelle im String sehr gut lösen.

So habe ich das bei infix-Notation genauso wie bei PN oder UPN gemacht. Bei dieser Vorgehensweise konnte ich den Baum dann auch symbolisch analysieren und auswerten, genauso wie Variablen einsetzen, eine Funktion symbolisch ableiten usw.

Sprich du fängst am Anfang an und sagst: Werte mal aus.
Die Parserfunktion gibt dann jeweils einen Knoten zurück mit einem Wert oder mit einem Operator und zwei Werten. Diese beiden Werte sind dann wiederum Knoten. Sprich:
Die Funktion bekommt den Anfang übergeben. Entweder findet sie dann als erstes einen Operator, dann ruft sie sich selbst zweimal auf (und bekommt die beiden Operanden) oder sie findet einen Wert, dann gibt sie diesen einzeln ohne Operator zurück.

Teekeks hat folgendes geschrieben :

Edit: man könnte ja auch einfach nur das ganze von Hinten nach vorne interpretieren, dann scheint es das selbe wie die UPN zu sein.

Ganz genau!

Und 12 + 3 / 4 * 2 - 14 + 10
wird in PN dann zu
+ - + 10 14 / * 3 4 2?

Das ist nicht mal gültig...



Aus Pi (jaja ich weiß, ich bin faul.):




Das ist allerdings AFAIK nicht die einzige Variante, wie man den Ausdruck schreiben kann. Hängt halt davon ab, wie man gleichwertige Operatoren auf der gleichen Stufe sortiert (also (a+b)+c oder a+(b+c)). Pi ist linksassoziativ, du bekommst also immer die erste Variante.

Danke martok, jetzt hab ich das kapiert (und in 30 Min einen immerhin schon mal funktionierenden parser für die Grundrechenarten hingelegt o0).

Danke für die Hilfe an euch beide!