Komplexe Funktionsterme zu Postfix konvertieren

[Nils_13]

Hi!

Dieses Thema gehört in keines der vorhandenen Foren. Mein Problem ist kein Programmierproblem sondern ein mathematisches. Ich halte ein Mathematik-Forum für angemessen da Programmieren ohne Mathematik unmöglich ist. Ich habe diese Frage einfach in dieses Forum gepackt, weil ich "Programmieren allgemein" für genauso schwachsinnig halte und ich einfach in dieser Kategorie laut meinem Profil wohne :P

Ich konvertiere erfolgreich Infix zu Postfix. Nun stehe ich allerdings vor einem Problem:
Hat man eine Funktion namens fnkt(20), dann schreibt man einfach 20 fnkt in Postfix. Aber nun nehmen wir mal an, ich hätte fnkt((2/5^2)*6). Dann wäre das 2 5 2 ^ / 6 * fnkt. Wie soll ich am Ende

Code:

2 5 2 ^ / 6 * fnkt

noch vom Rest unterscheiden können ? Woher soll ich wissen, wie weit ich in den Stack reingehen muss, um den kompletten Funktionsterm zu bekommen ?

Eine Lösung wäre natürlich, denn Funktionsterm zu Postfix zu konvertieren, diesen auszurechnen und am Ende vor den Funktionsnamen schreiben (am Beispiel von oben verdeutlicht):

Code:

0,48 fnkt

Aber ich finde das ist nicht zufriedenstellend, da ich auf einen kompletten UPN-Term großen Wert lege.

Habt ihr eine Idee wie man dieses Problem lösen könnte ?

[Apollonius]

Wie wertest du denn aus? Normalerweise geht man bei Postfix doch so vor, dass man von links nach rechts den Term durchgeht, dabei jeden Operanden auf einen Stack legt und bei jeder Operation zwei Operanden vom Stack nimmt und das Ergebnis darauflegt. Wenn du einem Funktionsnamen begegnest, musst du das Argument einfach nur noch vom Stack holen.

Ich hoffe mal, dass das nicht am Thema vorbeigeschrieben war.

[Nils_13]

Angenommen ich gehe hier von links nach rechts durch, treffe ich zuerst auf den Funktionsnamen:
sin(...)
Was soll ich da vom Stack holen ?

[Apollonius]

In der Postfix-Notation muss jede Operation immer rechts von ihren Operanden stehen. Wenn du also einem Funktionsnamen begegnest und nichts auf dem Stack liegt, dann ist der Term ungültig.

[Nils_13]

Ah, ich glaube jetzt habe ich endlich verstanden was du meinst.

Mein erstes Ziel ist es ja, einen InfixToPostfix-Konverter zu schreiben. Angenommen mir konvertiert mein Konverter den Term

Code:

25*sin(2+2)

zu

Code:

25 2 2 + sin *

dann ließe sich doch theoretisch eine Funktion schreiben, die diesen Term tatsächlich auseinandernimmt, da man (so habe ich dich verstanden) bei einem UPN-Rechner (gemeint ist ein Parser der anschließend den Kram durchrechnet) von rechts nach links durchgeht, da die Operatoren nunmal rechts stehen. Bei dem UPN-Term ist dann ja trotzdem klar definiert, was mit was zu tun hat.

Habe ich dich richtig verstanden ?

[Apollonius]

Normalerweise geht man von links nach rechts - das ist einfacher. Wenn du deinen letzten Term so durchgehst, sieht das so aus (die Stackoberseite ist immer links):

Code:

1. 25
2. 2  25
3. 2  2  25
4. 4  25
5. sin(4) 25
6. sin(4)*25

Prinzipiell kannst du auch von rechts nach links gehen. Dann brauchst du allerdings Rekursion, weil du die Argumente deiner Funktionen und Operationen noch nicht kennst.

[jfheins]

Ich weis nicht, wo dein Probelm liegt :wiejetzt:

Bei dem Term 25 2 2 + sin * passiert doch folgendes:

push (25) // 25
push (2) // 25 ; 2
push (2) // 25 ; 2 ; 2
push(pop + pop) // 25 ; 4
push(sin(pop)) // 25 ; -0,757
push(pop * pop) // -18,92

pop liefert das oberste Element, push legt das element oben ab

So - wo war jetzt das Problem) binäre von unären Operatoren zu unterscheiden?

[Khabarakh]

Zitat:

Zitat von Nils_13

bei einem UPN-Rechner (gemeint ist ein Parser der anschließend den Kram durchrechnet) von rechts nach links durchgeht, da die Operatoren nunmal rechts stehen.

Von links nach rechts, wie er in #2 geschrieben hat.
Da das noch nicht klar zu sein scheint, mal ein Beispiel an deinem Beispiel ;) :
Links die restlichen Token, rechts der Stack

Code:

25 2 2 + sin *  |
2 2 + sin *     | 25
2 + sin *       | 25 2
+ sin *         | 25 2 2
sin *           | 25 4
*               | 25 -0,757
                | -18,9

/edith: Rote Kästen sind schon toll :gruebel: .

[Nils_13]

Ah, heute bin ich wieder blöd. Ist jetzt alles klar, vielen Dank!