Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Polnische / Umgekehrt Polnische Notation
Kann mir jemand kurz erklären, wie man am leichtesten und verständlichsten auf diese beiden Notationen kommt?
Vielleicht anhand folgenden Beispiels:
a-b-c
a*b-a/(c+d)
Danke.
a-b-c
polnisch:
– a b c
umgekehrt polnisch:
a b - c -
a * b-a / (c+d)
polnisch:
/ * a - b a + c d
umgekehrt:
b a - a * c d + /
Naja, ich versuch mal die UPN anhand des letzten Beispiels zu erklären.
Das ganze hat HP ja für ihre Taschenrechner entwickelt, die wohl mit Stacks arbeiten.
Also zuerst packst du b, a in den Stack, dann kommt ein Operand. Dieser nimmt die obersten beiden Zahlen und “operiert” diese (b-a) und das ergebnis liegt alleine auf dem Stack. Dann packst du ein a drauf und wieder einen operanden (*) und der Taschenrechner “operiert” wieder die beiden obersten Zahlen auf dem Stack [(b-a)*a)] und legt das Ergebnis ab (zur Zeit ist also nur das Ergebnis im Stack…).
Dann packt er wieder 2 Zahlen drauf (c&d) und operiert mit + die beiden obersten Zahlen und legt das Ergebnis ab. Im Stack stehen jetzt der Nenner und (c+d). Jetzt wirfst du wieder einen Operand drauf (/) und der Taschenrechner verwurstet auch noch die letzten beiden Zahlen auf dem Stack.
Die normale Notation ist das gleiche in Grün, nur dass du die Operanden VOR die Zahlen schreibst.
Ich seh gerade, dass war eine Klausuraufgabe von '02. Wieso mussten die Jungs da schon Assemblerzeugs mit Registern können? Kommt das bei uns auch?
Danke für die schnelle Hilfe.
Ich hab das Registerzeugs noch nicht gefunden, also wirds wohl nicht kommen.
Kann man anhand des Syntaxbaums auch die Notationen ablesen?
Keine Ahnung, ehrlich gesagt hab ich das nur kurz bei google rausgesucht. Ist aber eigentlich recht easy zu kapieren, wenn du dir das mit dem Stack vorstellst.
Berechnet
/ * a - b a + c d
nicht den Infix-Ausdruck
a * (b - a) / (c + d) ??
Ups, stimmt. Wobei ich das auch so verstanden hatte. Richtig wärs dann natürlich so:
/ - * a b a + c d
und die umgekehrte Variante ist dann natürlich auch falsch:
statt:
b a - a * c d + /
wäre das dann:
a b * a - c d + /
Wie schauts dann bei
a - b * c / b * e
und
b + c / b + e * c
aus?
Nutze die Macht, junger Padawan.
Probiers erstmal mit der UPN aus:
a-(b*(c/b)*e)
a c b / b * e * -
und die normale:
- a * * / c b b e
und die andere:
b+(c/b)+(e*c)
UPN:
b c b / + e c * +
PN:
-
- / c b b * e c
PS: Keine Gewähr auf Richtigkeit, ich hab die Aufgabe jetzt mal so geklammert wie ich sie verstanden habe und ich hab keine Ahnung wie das wirklich geht. Gib einfach mal bei google was ein von wegen polnischer Notation, da kommst du auf 1000 Seiten mit Beispielen.
PPS: Es gibt glaube ich mehrere Lösungen, zB:
statt:
b c b / + e c * +
müsste auch gehen:
e c * b c b / + +
is ja eigentlich auch logisch 
Danke. Jetzt hats geschnaggelt.
Da kann ich mir die 1000 google Seiten sparen! 
mal ne frage, wuerde dann fuer
a * b-a / (c+d)
auch
-*ab/a+cd
bzw.
ab*acd+/-
gehen?
thx
Denke schon
ich versuch das mal anhand von deinem stack-verfahren nachzuvollziehen:
a
a b
a b * --> (a*b)
(a*b) a
(a*b) a - --> ((a*b)-a)
((a*b)-a) c
((a*b)-a) c d
((a*b)-a) c d + --> ((a*b)-a) (c+d)
((a*b)-a) (c+d) / --> (((a*b)-a)/(c+d))
und das stimmt nicht ueberein mit der angabe (geklammert):
(a*b) - (a/(c+d))
oder?btw: bei der UPN: seid ihr sicher, dass ab- infix (a-b) bedeutet und nicht (b-a)? die beispiele im skript sind schlauerweise alle kommutativ, sodass man sowas nicht rausfinden kann…
@jason: also meiner meinung nach ist deines nicht nur EINE richtige loesung, sondern DIE richtige!
gut zu wissen, alles andere hat mich hier nur verwirrt