Quelle est la signification de la notation polonaise inversée?

J'enseigne l'informatique à des jeunes de 18 ans. Après avoir expliqué la notation polonaise inversée, on a demandé pourquoi elle était suffisamment importante pour être soumise à l'examen public. J'ai expliqué l'importance historique des calculatrices des années 70, mais cela n'a pas vraiment résolu le problème. Il en est de même des applications pratiques ou théoriques simultanées du RPN.

J'ai utilisé RPN plusieurs fois pour le prototypage rapide, par exemple des programmes qui doivent lire et interpréter une expression mathématique fournie par l'utilisateur.

Alors que la notation mathématique régulière nécessiterait au moins un analyseur récursif (pensez aux crochets, à l'ordre des opérateurs, etc.), un analyseur RPN est essentiellement une pile avec une switchinstruction de type. Je suppose que c'est cette combinaison de simplicité et de puissance expressive qui a conduit HP à l'utiliser initialement.

C'est, cependant, généralement pour un prototypage rapide et pour plus de commodité. Je ne suppose jamais qu'un utilisateur peut ou veut comprendre RPN.

Juste pour développer les réponses / commentaires précédents: n'oubliez pas que RPN est vivant et en pleine forme ... en effet, il est actuellement utilisé dans des machines de pile comme la machine virtuelle Java.

De Wikipedia: "... une machine de pile implémente une pile avec des registres. Les opérandes de l'unité logique arithmétique (ALU) sont toujours les deux premiers registres de la pile et le résultat de l'ALU est stocké dans le registre supérieur de la pile . «Machine à pile» fait généralement référence aux ordinateurs qui utilisent une pile dernier entré, premier sorti pour conserver des valeurs temporaires de courte durée lors de l'exécution d'instructions de programme individuelles. Le jeu d'instructions exécute la plupart des actions ALU avec des opérations postfix ( notation polonaise inversée ) qui fonctionne uniquement sur la pile d'expression, pas sur les registres de données ou les cellules de mémoire principale ... "

Les avantages / inconvénients d'une telle approche sont également décrits dans l'article Wikipedia .

Forth et PostScript (et donc PDF que l'IIRC a commencé comme encodage binaire d'un sous-ensemble de PostScript) sont des langages postfix plus connus que celui de la calculatrice de poche HP.

Ensuite, c'est aussi un choix relativement courant comme représentation intermédiaire dans des compilateurs simples.

La machine virtuelle plus simple a également tendance à avoir un langage "machine" postfixé.

En ce qui concerne les calculatrices: Voir Qu'est-ce que RPN?

• Avantages: RPN économise du temps et des frappes. Vous évitez d'utiliser et de suivre les parenthèses lors des calculs. Le processus est similaire à la façon dont vous avez appris les mathématiques sur papier.

• Vous pouvez voir les résultats intermédiaires lorsque vous effectuez vos calculs plutôt que simplement la réponse à la fin. C'est extrêmement utile pour apprendre la logique. Les professeurs de mathématiques utilisent cette fonction pour améliorer la compréhension des mathématiques par les élèves.

• Un résultat intermédiaire permet à l'utilisateur de vérifier la réponse et de corriger plus facilement les erreurs. Il est plus facile de suivre le flux de calcul. L'utilisateur définit la priorité des opérateurs.

• Le RPN est logique parce que l'utilisateur donne d'abord le numéro puis dit quoi en faire.

Comme son nom l'indique, la notation polonaise inversée ou la notation polonaise directe sont des notations. Ils sont une syntaxe pour représenter quelque chose et une syntaxe réellement efficace si vous considérez les besoins en mémoire. Ce qu'ils représentent sont des arbres enracinés, qui peuvent être des formules, des arbres de syntaxe abstraite (AST) et d'autres types d'entités, que toute personne a le droit constitutionnel de considérer comme absolument inutiles.

Parfois, il faut stocker ces entités dans un fichier. Par exemple, il existe des systèmes qui peuvent éditer ou transformer des programmes en AST et peuvent avoir besoin de stocker de telles représentations. La forme polonaise est pratique. Il a une lisibilité limitée pour les humains, en particulier pour les grands arbres, mais c'est une représentation très pratique pour les machines.

Un autre aspect est que je pense que l'étude des arbres et de leurs utilisations et représentations élémentaires, ainsi que des dispositifs associés (piles), est pédagogiquement utile comme introduction aux futures études de concepts plus avancés (syntaxe, analyse syntaxique, logique, linguistique). , ...).

Il a également l'avantage d'être conceptuellement assez simple et facile à expérimenter sur papier. C'est aussi une belle occasion de discuter de la syntaxe et du fait que la syntaxe est une représentation, et que les représentations peuvent varier, tout en représentant la même chose, et que différentes représentations peuvent être utilisées selon le besoin à satisfaire (optimisation de l'espace, modification facile, lisibilité humaine, lisibilité informatique, ...).

Mais je suis surpris que cette question, et ses réponses, ne prennent en compte que le RPN, et aucune ne considère la notation polonaise directe.

C'est certainement excellent que les étudiants demandent. Mais répondre à une telle question a toujours des aspects divers. Est-ce utile pour la connaissance elle-même? Je pense que c'est. Est-ce utile comme exercice pédagogique? Je pense que oui, mais cela dépend beaucoup du public visé, et seul l'enseignant peut évaluer ce qu'il est capable de comprendre. Est-il utile de comprendre certains problèmes conceptuels? Je pense que oui, mais encore une fois, cela dépend de l'évaluation par l'enseignant des concepts qui peuvent être expliqués à leurs élèves.

Votre élève avait absolument raison. La notation polonaise inversée n'est pas suffisamment importante en informatique pour valoir la peine de passer très peu de temps en classe. Au lieu de cela, il y a tellement d'autres merveilleuses idées conceptuelles que vous auriez pu enseigner, avec des idées intellectuelles profondes: mariage stable, coupe de gâteau, diagonalisation et indécidabilité du problème d'arrêt, preuves interactives et preuves de connaissance zéro, etc., etc. Oui, tout cela peut être rendu accessible aux jeunes de 18 ans.

Et j'espère que vous avez félicité votre élève d'avoir eu le courage de poser la question! Ils ont dû se mettre sur un rebord pour soulever la question. Cela montre bien pour votre style d'enseignement qu'ils se sentaient à l'aise de vous poser cette question.

La notation polonaise inversée était un bon outil dans mon éducation pour comprendre les arbres d'analyse et les structures de données d'arbre en général. Il est également utile si quelqu'un s'intéresse à la programmation dans l'un des langages Lisp (Clojure, emacs-lisp, schéma, etc.).