Diskussion:Umgekehrte polnische Notation

Hab diese zwei Absätze rausgenommen:

Die Infix- und die Postfix-Notation sind beide eindeutig. Die Infix-Notation benötigt aber sehr viele Regelen, die Postfix-Notation sehr wenige. Die Auswertung von Ausdrücken in Infix-Notation im Computer ist programmiertechnisch sehr aufwendig.

Bei der Verarbeitung mathematischer Ausdrücke ist deshalb die Postfix-Notation für Computer eigentlich besser geeignet.

Der letzte Satz klingt mir zu sehr nach dem alten Taschenrechner-Streit ("Mein HP ist aber besser als dein TI"), da fehlt mir der neutrale Standpunkt. Zudem gibt es auch klammerfreie Infix-Notationen, das macht jeder billig-Taschenrechner. Die ist noch einfacher zu realisieren und kommt ohne Stack aus. Die vielen Regeln sind auch nicht infix-spezifisch, sondern eine Besonderheit der arithmetischen Notation. Flups 11:33, 8. Okt 2002 (CEST)

Das stimmt so nicht ganz. Man braucht auch zum Parsen der Infix-Notation einen Stack. Ohne Stack kommt man nur bei Regulären Sprachen aus. MlaWU 22:11, 8. Jun 2004 (CEST)

Frage: Sind die Ausdrücke "Umgekehrte Polnische Notation" bzw. "Reverse polish notation" im Artikel wirklich keine Missverständnisse? Aus funktionaler Sichtweise ist der Ausdruck +(a,b) richtigherum, da er von links nach rechts gelesen wird und genauso ausgewertet werden kann. Der Ausdruck (a,b)+ ist aus funktionaler Sichtweise falschrum, da er funktional von rechts nach links gelesen werden muss. Des weiteren werden die Attribute "rückwärts", "falschrum" oder "polnisch" oft (scherzhaft) synonym verwendet, da Polnisch für (viele) Nichtpolen (ist wirklich nicht diskriminierend gemeint) ähnlich exotisch aussieht, als würde man die eigene Landessprache rückwärts schreiben. Analog dazu wäre eine korrekte Bezeichnung für den Ausdruck (a,b)+ : "polnische Notation" oder "umgekehrte Notation". Will man beide Attribute affirmativ verwenden, so muss man ein Komma zwischen sie Setzen und "umgekehrte, polnische Notation" schreiben. Der Ausdruck "Umgekehrte polnische Notation" (ohne Komma) steht doch für einen konsequent, logisch denkenden Menschen für: umgekehrt(polnisch((+(a,b)))) -> umgekehrt((a,b)+) -> +(a,b) also wieder für die ursprüngliche funktionale Schreibweise!? Was meint ihr da draußen? DFK 23:23, 7. Mär 2004 (CET)]]

Über das Komma könnte man streiten. Ich denke "Umgekehrt polnische Notation" ist eine feststehende Bezeichnung und daher so in Ordnung. "umgekehrte Notation" oder "polnische Notation" ist jedenfalls nicht das, was hier gemeint ist.Hweihe 14:52, 9. Apr 2004 (CEST)

Soweit ich mich erinnere, hat derjenige, der die anderen Schreibweisen entwickelt hat, zuerst eine Präfix-Notation gehabt, die als "polnische Notation" bezeichnet wurde. Später kam man dann auf die Postfix-Notation, die dann "umgekehrte polnische Notation" genannt wurde. Diese Notation ist auch nicht "umgekehrt polnisch", sondern wirklich eine Umgekehrung der polnischen (Präfix-)Notation. Die Bezeichnung "polnische Notation" für die Postfix-Notation ist mir noch nicht begegnet. --SirJective 12:28, 10. Apr 2004 (CEST)

Im Grundstudium wurde uns erzählt, daß die polnische Notation im 19. Jahrhundert von irgendeinen Polen entwickelt wurde. Ziel war wohl etwas klammerfreies zu haben. Als dann irgendwann Computer aufkamen hat man festgestellt, daß sich Operationen in Postfix-Notation sehr einfach mit einer Stackmaschine verarbeiten lassen und das ganze umgedreht. Ich kenne das aber nur unter dem Begriff "Inverse Polnische Notation" (IPN). MlaWU 16:28, 29. Apr 2004 (CEST)

Genau, das habe ich auch im Grundstudium gehört. Der Pole hieß Lukasiewicz. Ich habe diese Geschichte einfach mal hinzugefügt. Vieleicht sollte der Text aber auch noch umgestellt werden. Zum Teil stehen diese Sachen auch im Artikel Notation (Mathematik). Frage: Sollte man die Themen (umgekehrte? polnische|(prä|in|post)fix)-Notation nicht besser in einem statt in mehreren Artikeln parallel beschreiben? rara 02:34, 2. Jun 2004 (CEST)

Im englischen Beitrag en:Reverse Polish Notation steht ein anderer Erfinder der UPN. Wer weiß, was richtig ist? Ralf Pfeifer 16:37, 13. Jun 2004 (CEST)

Das Museum von HP gibt uns Recht: http://www.hpmuseum.org/rpn.htm Ich habe aber auch Seiten gefunden, die den Australier erwähnen. Ich würde mal vermuten, daß der das ganze Jahre später unabhängig von dem Polen wiederentdeckt hat. Sowas passiert durchaus öfter. Wie gesagt, ist nur eine Vermutung. Ich habe eben mal beim Zentralblatt für Mathematik nach der Originalarbeit gesucht, aber nichts aus dem Jahr 1920 gefunden. Es gibt aber eine Arbeit mit dem Titel "Logika dwuwartosciowa." aus dem Jahr 1921. Da ich aber kein polnisch kann, kann ich da auch nichts nachprüfen. MlaWU 20:00, 13. Jun 2004 (CEST)

Da ein Student nachfragte - er nannte Hamblin, ich kenne nur Tarski und Lukasiewicz. Ich habe etwas recherchiert:

Knuth, Fundamental Algorithms, 1973 (!)
p. 336: "Algabreic expressions like (8) [preorder] and (9) [postorder]
are very important and they are known as 'Polish notations' because
form (8) was introduced by the Polish logician Lukasiewicz."
Aho/Ullman, "Theory of Translation", 1972, footnote page 214
"The term 'Polish' is used, as this [two forms, prefix Polish and 
postfix Polish] notation was first described by the
Polish mathematician Lukasiewicz, whose name is significantly
harder to pronounce than is 'Polish'"
Bauer/Goos, "Informatik, Eine einführende Übersicht, Erster Teil", 
Springer-Verlag:Berlin, 1982, S. 224
"Eine klammerfreie Präfixschreibweise, auch 'Warschauer Normalform'
(engl. Polish notation) genannt, wurde eingeführt in der Schule des 
polnischen Logikers Lukasiewicz um 1925. Die hier auftretende 
klammerfreie Postfixschreibweise wird auch 'reverse Polish
notation' genannt" 
Hewlett-Packard:
http://www.hpmuseum.org/rpn.htm
"Prefix notation also came to be known as Polish Notation in honor of Lukasiewicz. HP adjusted the postfix 
notation for a calculator keyboard, added a stack to hold the operands and functions to reorder the stack. H P 
dubbed the result Reverse Polish Notation (RPN) also in honor of Lukasiewicz."

Auch Langmaack/Hill/Grau verwendeten den Begriff "Umgekehrte Polnische Notation" in 1957, Hamblin hat erst 1962 publiziert. Kann also nicht so recht sein, dass er das entdeckt hat :) --WiseWoman 14:25, 6. Jan. 2008 (CET)

Oops, 19*6*7. Okay, kann noch sein, aber ich denke auch: unabhängig von einander "entdeckt". --WiseWoman 14:27, 6. Jan. 2008 (CET)

Taschenrechnerlastigkeit

Mir ist dieser Artikel viel zu Taschenrechnerlastig. Falls es keine Einsprüche gibt (und ich mal wieder etwas Zeit habe), werde ich den Kram demnächst mal kürzen und durch ein paar Erklärungen des Stackverfahrens ersetzen. MlaWU 20:03, 13. Jun 2004 (CEST)

Beispiel richtig?

Im Artikel steht:

Beispiel in der bekannten Notation: 3 + 4 × 5 = 3 + (4 × 5), weil die Multiplikation Vorrang vor der Addition hat.

Bei der UPN können solche Regeln entfallen, alle Operationen arbeiten mit den beiden oberen Elementen des Stack. Das Beispiel oben heißt in UPN: 3 4 5 × +

Muß es nicht 3 4 5 + × heißen? --Kookaburra 15:56, 27. Dez 2004 (CET)

Es ist richtig. Der Ausdruck wird Zeichen für Zeichen abgearbeitet. Wenn eine Zahl gefunden wird, wird sie in den Keller getan. Wenn ein Operationszeichen gefunden wird, wird es auf die im Stapel obenliegenden Elemente angewandt (wobei diese aus den Keller entfernt werden). Das Ergebnis wird dann wieder auf den Stapel gelegt. Wenn man also 3 4 5 * + abarbeitet passiert folgendes (links das gerade verarbeitete Zeichen, rechts der Stapel):

3 | 3
4 | 3 4
5 | 3 4 5
* | 3 20
+ | 23

Das Plus hat also die beiden Operanden 3 und 4 5 *. MlaWU 14:55, 28. Dez 2004 (CET)

Nö, irgendwas stimmt hier nicht. Wenn ich den Syntaxbaum zu dem Beispiel aufstelle, sieht er wie folgt aus:

    +
   / \
  *   3
 / \
4   5

Wenn man diesen nun in Postorder durchläuft, erhält man folgenden Postfix-Ausdruck: 45*3+ Und so wird das meines Erachtens auch abgearbeitet. Zuerst werden 4 und 5 auf den Stack gelegt, dann das * gelesen, berechnet und das Zwischenergebnis (20) auf den Stack gelegt. Danach wird die 3 auf den Stack gelegt, das + gelesen und berechnet. Das Ergebnis ist 23. --84.180.213.45 4. Jul 2005 22:38 (CEST)

Und wofür brauchst Du dann den Stack? (mal abgesehen von der Tatsache, daß Dein Parser nicht ohne auskommt) -- MlaWU 5. Jul 2005 01:50 (CEST)

Holger Weihe 6. Jul 2005 22:11 (CEST) Eingabe in einen HP-Rechner: 3 Enter 4 Enter 5 Enter x +

ergibt definitiv 23. 3 4 5 + x ergibt 27, ist also nicht die gewünschte Rechnung.

Auch komisch: Wenn ich den Syntaxbaum zu dem Beispiel 3 + (4 × 5) aufstelle (und da glaube ich mit den meisten Parsern einig zu sein), sieht er so aus:

    +
   / \
  3   *
     / \
    4   5

Will sagen, linke Operanden sollten auch links bleiben...
Wenn man _diesen_ Syntaxbaum in Postorder durchläuft, kommt auch ganz korrekt 345*+ heraus.

-- Thomas Haupt 19. Aug 2005 11:40 (CEST)

UPN an Schulen

Rechnen Kinder in Polen im Mathematikunterricht mit der UPN? Danke, --Abdull 12:26, 28. Feb 2005 (CET)

sicherlich nicht :-) --MlaWU 20:34, 28. Feb 2005 (CET)

Aber sicher doch, genau wie auch in Deutschland und im Rest der Welt. Zwar wird algebraisch Notiert, doch beim rechnen, folgen wir dann der Eingabeweise der UPN.

Beispiel: (5+3) * (5+5)

Zuerst werden 5 und 3 addiert [5 3 +] , dann 5 und 5 addiert [5 5 +] und anschließend die beiden Zwischenergebnisse multipliziert [*]. Die UPN Eingabe entspricht selbst bei komplizierten mathematischen Termen immer der menschlichen Rechenweise.

Ich kann das nur bestätigen. Der zu berechnende Ausdruck kann die verwirrensten Klammerebenen und Funktionen besitzen und man hat dennoch nie mehr als vier Zahlen gleichzeitig im Stapel. Allerdings wird man durch die UPN gezwungen, sich den zu berechnenden Ausdruck zuvor genau anzusehen und die Berechnung dann bei der innersten Klammerebene zu beginnen. Dieser Zwang zur vorherigen Analyse des Ausdruckes ist aber kein Nachteil, sondern schult in gewisser Weise das Erkennen von mathematischen Lösungswegen. --Markus Schweiß| @ 18:57, 22. Feb. 2007 (CET)

weiterer Nachteil

Ist es möglich mit der UPN Funktionen zu überladen? Ich kann es mir nicht vorstellen. D.h. das implementieren von komplexeren Funktionen, bei denen auch nicht alle Parameter mitgegeben müssen ist nicht möglich.

z.B. f(a, b [, c][, d]) Wie will ein Rechner so wissen, ob er die ersten 2, 3 oder 4 Zahlen im Stack verarbeiten soll?

Es ist natürlich möglich. Das genannte Beispiel hat allerdings nichts mit Überladung zu tun, sondern bezeiht sich auf "Funktionen mit variabler Parameterzahl". Um so etwas zu ermöglichen, gibt es mehrere Möglichkeiten.

1. Ein Markierungsobjekt auf dem Stack. Die Funktion konsumiert solange Parameter von Stack, bis sie auf die spezielle Markierung stösst. Ich weiss, dass ich das schon mal gesehen habe, aber ich bin mir nicht mehr sicher, wo. Kann es sein, dass Postscript das bietet? --Klaws 00:35, 11. Dez 2005 (CET)

Ja. Der „[“- bzw. „mark“-Operator legt eine Markierung auf den Stack. Der „]“-Operator schließlich verbraucht alle Operanden bis zur Markierung und bildet ein Array daraus. Daher bilden die PS-Befehle „[ 1 2 3 add ]“ ein Array mit zwei Zahlen, und zwar 1 und 5. -- Pemu 14:00, 15. Jun. 2007 (CEST)

2. Ein Zusatzparameter, der angibt, wieviele Parameter übergeben werden. Gut bekannt aus der klassischen C-Programmierung von der Funktion printf(). Die printf-Funktion erkennt einzig und allein an der Anzahl der Formatkennzeichen in ersten Parameter, wieviele weitere Parameter folgen (heutzutage führen die C-Compiler eine Plausibilitätsprüfung durch, ob die tatsächliche Parameterzahl zum ersten Argument passt - denn wenn die nicht zusammen passen, gerät während der Laufzeit der Stack übelst durcheinander).

3. Durch die Verwendung eines Listenobjekts. Die Liste belegt eine Position auf dem Stack und enthält alle Parameter. Das kann z.B. so aussehen:

#( 1 6 2 9 5 3 ) average

Na, wer erkennt die Programmiersprache? :-)

Für Taschenrechner ist Option 2 die wohl praxisgerechteste. Man muss halt beim "Parametersammeln" mitzählen; dafür erspart man sich das "Zusammenfrickeln" eines Listenobjekts bzw. das nachträgliche Platzieren eines Markers auf dem Stack (man könnte ihn natürlich auch vorausschauend platzieren, aber eienr der Hauptvorteile von UPN ist ja eigentlich, dass man kein vorausschauendes Eintippen benötigt).

Der HP-28 war der erste "objektorientierte" UPN-Rechner, den ich kennen lernte (Ende der 80er). Sprich, er konnte nicht nur Zahlen auf den Stack packen, sondern auch andere Objekte (Arrays, Listen, komplexe Zahlen, etc pp). Dieser Taschenrechner setze teilweise Option 2, teilweise Option 3 ein. Und selbstverständlich waren auch alle Funktionen werksmäßig überladen, wo dies mathematisch möglich war (bei früheren Rechnern gab es z.B. neben der normalen Multiplikation auch eine spezielle Multiplikation (mit anderem Namen) für komplexe Zahlen, wieder eine andere für Matrizen...beim HP-28 war das alles in der "normalen" Multiplikationsfunktion enthalten (sprich: überladen)). --Klaws 00:35, 11. Dez 2005 (CET)

Modelle

Mit Ausnahme des seit 1981 erhältlichen reinen UPN-Taschenrechners HP 12C und einiger rein algebraischer Geräte im unteren Preisbereich unterstützen die Anfang 2007 neu auf den Markt gekommenen HP-Taschenrechner wie der HP-50g beide Eingabenotationen.

Der Satz hat keinen Sinn, denn der seit 1981 erhältliche Rechner ist sicher nicht Anfang 2007 neu auf den Markt gekommen. Falls jemand vollständige und richtige Infos hat, bitte korrigieren. --Diwas 00:03, 13. Jul. 2007 (CEST)

Wirklich wahr?

Es ist erwiesen, dass sich beliebig komplexe mathematische Berechnungen mit einem Stapel von nur vier Einträgen ausführen lassen

Das kann ich kaum glauben. Aber auch wenn es wahr sein sollte, wäre ein Verweis zu einem Beweis angebracht. Kann es evtl. sein, dass nur bestimmte Ausdrücke gemeint sind? Z. B. solche, die nur aus +, - , * und / bestehen.