Welche Bedeutung hat die umgekehrte polnische Notation?

21

Ich unterrichte Computer für 18-Jährige. Nachdem man ihnen die umgekehrte polnische Notation erklärt hatte, fragte man sie, warum es wichtig genug sei, an der öffentlichen Prüfung teilzunehmen. Ich habe die historische Bedeutung von Taschenrechnern der 70er Jahre erklärt, aber dies hat das Problem nicht wirklich gelöst. Gibt es also und gleichzeitig praktische oder theoretische Anwendungen von RPN.

Matt Scott
quelle
3
Ich programmiere seit fast zehn Jahren und habe einen Master in CS abgeschlossen, aber ich glaube nicht, dass ich jemals in einem ernsthaften Kontext Reverse Polish gesehen oder angewendet habe. Sind Sie sicher , es ist relevant, insbesondere für die Ausbildung von Studenten?
Raphael
Hier ist eine Implementierung eines Moduls für reguläre Ausdrücke, das die Postfix-Notation verwendet: swtch.com/~rsc/regexp/regexp1.html#thompson . Ken Thompson verwendete es auch in seiner ersten Implementierung. Es ist auch eine beliebte Technik zum Auswerten von Ausdrücken zur Laufzeit (wenn Sie einen Compiler erstellen).
Saadtaame
In RPN können Sie jeden Ausdruck ohne eckige Klammern aufschreiben.
Seg Fehler
3
Der Wikipedia-Artikel über RPN deckt viel Boden ab. Logiktexte beziehen sich manchmal auf die polnische Notation (weil sie frei von Klammern ist), wenn sie erklären, was in Beweisen als reiner "syntaktischer Zucker" weggelassen werden kann. RPN ist jedoch aufgrund seiner engen Beziehung zu Stacks wichtig. Das Verständnis von Stacks ist wichtig für das interaktive Debuggen, da der berühmte "Backtrace" normalerweise nur ein Stack-Dump ist. Reine funktionale Sprachen haben immer noch Schwierigkeiten, etwas zu bieten, das mit einem Stack-Dump zum Debuggen vergleichbar ist, obwohl sie viel detailliertere Informationen zu bieten hätten (wenn sie diese darstellen könnten).
Thomas Klimpel
Ich muss meinen früheren Kommentar teilweise zurückziehen. Ich habe jemanden gesehen, der Post-Fix-Notation für das Ablegen von Strings verwendet. Es war schrecklich zu lesen, aber leicht zu codieren. In ganz bestimmten Anwendungsfällen mag RP nützlich sein, aber ich bin mir nicht sicher, ob dies (im Allgemeinen) auch für den Bildungsbereich gilt. Sie können es verwenden, um zu zeigen, dass die Syntax nicht festgelegt ist, denke ich.
Raphael

Antworten:

9

Ich habe RPN mehrmals für Rapid Prototyping verwendet, z. B. für Programme, die einen vom Benutzer bereitgestellten mathematischen Ausdruck lesen und interpretieren müssen.

Während die reguläre mathematische Notation mindestens einen rekursiven Parser (Klammern, Operatorreihenfolge usw.) erfordern würde, ist ein RPN-Parser im Grunde ein Stapel mit einer switchähnlichen Anweisung. Ich denke, es ist diese Kombination aus Einfachheit und Ausdruckskraft, die HP dazu veranlasste, es anfangs zu verwenden.

Dies dient jedoch in der Regel dem schnellen Prototyping und der Benutzerfreundlichkeit. Ich würde niemals annehmen, dass ein Benutzer RPN verstehen kann oder will.

Pedro
quelle
8

Nur um die vorherigen Antworten / Kommentare zu erweitern: Vergessen Sie nicht, dass RPN lebendig und in hervorragender Form ist ... tatsächlich wird es derzeit in Stack-Maschinen wie der Java Virtual Machine verwendet.

Aus Wikipedia: "... eine Stapelmaschine einen Stapel mit Registern implementiert. Die Operanden der arithmetischen Logikeinheit (ALU) sind immer die beiden obersten Register des Stapels, und das Ergebnis der ALU wird im obersten Register des Stapels gespeichert . ‚Stack - Maschine‘ bezieht sich allgemein auf Computer , die-First out ein Last-in, verwenden Stapel kurzlebige temporäre Werte zu halten , während einzelne Programmanweisungen ausgeführt werden . Der Befehlssatz trägt die meisten ALU Aktionen mit postfix aus ( Reverse Polish Notation ) Operationen, arbeiten nur mit dem Ausdrucksstapel, nicht mit Datenregistern oder Hauptspeicherzellen ... "

Die Vor- und Nachteile eines solchen Ansatzes sind auch in dem Wikipedia-Artikel beschrieben .

Vor
quelle
Hm, wenn Sie den Bytecode betrachten, sehen Sie nicht die RPN per se. Natürlich werden die Anweisungen in der Reihenfolge "nach dem Fixieren" angezeigt, aber das sieht in der Arithmetik nicht nach RPN aus, und der Grund dafür ist ziemlich klar. Registriermaschinen müssen auf die gleiche Weise vorgehen: Werte laden, dann kombinieren.
Raphael
5

Forth und PostScript (und damit PDF, das IIRC als binäre Codierung einer Teilmenge von PostScript gestartet hat) sind bekanntere Postfix-Sprachen als HP Pocket Calculator.

Dann ist es auch eine relativ häufige Wahl als Zwischendarstellung in einfachen Compilern.

Die einfacheren VMs haben in der Regel auch eine Postfix-Maschinensprache.

Ein Programmierer
quelle
Übrigens enthält der Ausdruck "einfachere VM" die JVM. Das Interessante an RPN ist, dass es die einfachste nützliche Stapelmaschine ist. Stapelmaschinen sind das, was wirklich interessant und nützlich und relevant ist.
Pseudonym
4

In Bezug auf Taschenrechner: Siehe Was ist RPN?

  • Vorteile: RPN spart Zeit und Tastatureingaben. Sie vermeiden es, während der Berechnungen Klammern zu verwenden und den Überblick zu behalten. Der Vorgang ähnelt dem, wie Sie Mathe auf Papier gelernt haben.

  • Sie können die Zwischenergebnisse sehen, wenn Sie Ihre Berechnungen durchführen, und nicht nur die Antwort am Ende. Dies ist äußerst hilfreich für das Erlernen der Logik. Mathematiklehrer verwenden diese Funktion, um das Verständnis der Schüler für Mathematik zu verbessern.

  • Ein Zwischenergebnis ermöglicht es dem Benutzer, die Antwort zu überprüfen und Fehler leichter zu korrigieren. Es ist einfacher, dem Berechnungsfluss zu folgen. Der Benutzer legt die Priorität der Operatoren fest.

  • RPN ist logisch, weil der Benutzer zuerst die Nummer angibt und dann angibt, was damit zu tun ist.

Guy Coder
quelle
3

Wie der Name schon sagt, handelt es sich bei der umgekehrten polnischen Notation oder der direkten polnischen Notation um Notationen. Sie sind eine Syntax für die Darstellung von etwas und tatsächlich eine effiziente Syntax, wenn Sie den Speicherbedarf berücksichtigen. Was sie darstellen, sind verwurzelte Bäume, bei denen es sich um Formeln, abstrakte Syntaxbäume (AST) und andere Arten von Entitäten handeln kann, die jeder als absolut nutzlos betrachten kann.

Gelegentlich muss man solche Entitäten in einer Datei speichern. Beispielsweise gibt es Systeme, die Programme als AST bearbeiten oder transformieren können und möglicherweise solche Darstellungen speichern müssen. Polnische Form ist bequem. Es ist für Menschen, insbesondere für große Bäume, nur eingeschränkt lesbar, für Maschinen jedoch sehr praktisch.

Ein weiterer Aspekt ist, dass ich der Ansicht bin, dass das Studium von Bäumen und ihrer elementaren Verwendung und Darstellung sowie der zugehörigen Geräte (Stapel) als Einführung in zukünftige Studien fortgeschrittener Konzepte (Syntax, Parsen, Logik, Linguistik) pädagogisch nützlich ist , ...).

Es hat auch den Vorteil, dass es konzeptionell eher einfach ist und sich leicht auf dem Papier experimentieren lässt. Es ist auch eine gute Gelegenheit, die Syntax und die Tatsache zu diskutieren, dass Syntax Repräsentation ist und dass Repräsentationen variieren können, während sie dasselbe darstellen, und dass verschiedene Repräsentationen verwendet werden können, je nachdem, welche Anforderungen erfüllt werden müssen (Speicherplatzoptimierung, einfache Modifikation, menschliche Lesbarkeit, Computerlesbarkeit, ...).

Aber ich bin überrascht, dass diese Frage und ihre Antworten nur RPN berücksichtigen und keine direkte polnische Notation berücksichtigt.

Es ist auf jeden Fall sehr gut, dass die Schüler fragen. Die Beantwortung einer solchen Frage hat jedoch immer verschiedene Aspekte. Ist es nützlich für das Wissen selbst? Ich denke, es ist. Ist es als pädagogische Übung nützlich? Ich denke, das ist es, aber das hängt sehr vom beabsichtigten Publikum ab, und nur der Lehrer kann beurteilen, was er verstehen kann. Ist es hilfreich, einige konzeptionelle Probleme zu verstehen? Ich denke, das ist es, aber es hängt auch hier von der Einschätzung des Lehrers ab, welche Konzepte den Schülern erklärt werden können.

babou
quelle
2

Ihr Schüler hatte absolut Recht. Die umgekehrte polnische Notation ist in der Informatik nicht signifikant genug, um eine sehr begrenzte Unterrichtszeit dafür aufzuwenden. Stattdessen gibt es so viele andere wunderbare konzeptionelle Ideen, die Sie mit tiefen intellektuellen Ideen hätten lehren können: stabile Ehe, Kuchenschneiden, Diagonalisierung und Unentscheidbarkeit des Halteproblems, interaktive Beweise und wissensfreie Beweise usw. usw. Ja, alle diese können für 18-Jährige zugänglich gemacht werden.

Und ich hoffe, Sie haben Ihren Schüler dafür gelobt, mutig genug zu sein, um die Frage zu stellen! Sie mussten sich auf einen Felsvorsprung stellen, um das Thema anzusprechen. Es spricht gut für Ihren Unterrichtsstil, dass sie sich wohl gefühlt haben, Ihnen diese Frage zu stellen.

DW
quelle
1
Das Unterrichten der polnischen Notation nimmt fast keine Zeit in Anspruch. Die Linearisierung von Standardstrukturen wie Bäumen ist ebenfalls von Bedeutung, da die Massenspeicherung häufig eher sequentiell als zufällig erfolgt. Möglicherweise möchten Sie es auch effizient speichern oder verstehen, wie Sie es ganz oder teilweise abrufen können. Es verbindet Bäume, Baumspaziergänge, eingebettete Strukturen und Pushdown. Abstrahiert erklärt es, wie Gödel-Codierungen für Daten erstellt werden. Im Vergleich zu der enormen Zeit- und Energieverschwendung, die durch LR- und LL-Analyse und andere Junk-Technologien verursacht wird, würde ich sogar sagen, dass die Zeit, die für die polnische Notation aufgewendet wird, gut angelegt ist.
Babou
"nicht signifikant genug in der Informatik" - unglaublich meinungslos
Dmitri Zaitsev
1

Die umgekehrte polnische Notation war ein gutes Werkzeug in meiner Ausbildung, um Analysebäume und Baumdatenstrukturen im Allgemeinen zu verstehen. Es ist auch nützlich, wenn jemand Interesse an der Programmierung in einer der Lisp-Sprachen hat (Clojure, Emacs-Lisp, Schema usw.).

user21796
quelle
Warum Lisp und Scheme? Sie sind voller Klammern.
Babou