Rpn

Rpn

Notation polonaise inverse

Page d'aide sur l'homonymie Pour les articles homonymes, voir NPI et RPN.

La notation polonaise inverse (NPI) (en anglais RPN pour Reverse Polish Notation), également connue sous le nom de notation post-fixée, permet de noter les formules arithmétiques sans utiliser de parenthèses. Dérivée de la notation polonaise présentée en 1920 par le mathématicien polonais Jan Łukasiewicz, elle s’en différencie par l’ordre des termes : les opérandes y sont présentés avant les opérateurs et non l’inverse.

Cette notation est en fait très proche de celle utilisée dans le calcul écrit.

Quels sont ses avantages ?

  • En programmation, chaque paire de parenthèses correspond à un calcul intermédiaire qu’il faudrait stocker quelque part. La NPI permet de gérer ces calculs intermédiaires sous forme de pile (alias LIFO pour last in, first out). Le passage par la NPI permet donc d’organiser plus facilement le travail d’optimisation du compilateur ;
  • Dans le cas d’une calculette, elle diminue le nombre de caractères à frapper, au prix d’un léger effort d’abstraction (écrire 2 2 + au lieu de 2 + 2 =). Accessoirement, à l’époque des premiers circuits intégrés, cela en diminuait aussi la complexité ;
  • Elle permet de voir les résultats intermédiaires et donc de détecter plus facilement d'éventuelles erreurs.

NPI a été inventé par le philosophe australien et informaticien Charles Hamblin dans le milieu des années 1950, pour permettre les calculs sans adresse mémoire[réf. nécessaire].

Elle a été utilisée pour la première fois comme interface utilisateur par les calculateurs de bureau d’Hewlett-Packard à la fin des années 1960 (HP9100), puis dans la calculatrice scientifique HP-35 lancée en 1972. Avec la NPI les opérandes précèdent l’opérateur, cette notation permet donc de se passer des parenthèses.

Par exemple, l’expression :
3 * (4 + 7)
s’écrira :
4 7 + 3 *
ou
3 4 7 + *
En pratique sur une calculatrice de NPI le calcul sera saisi en tant que :
« 4 », « entrée », « 7 », « + », « 3 », « * ».
ou
« 3 »,« entrée », « 4 », « entrée », « 7 », « + », « * ».

La réalisation de calculatrices NPI est basée sur l’utilisation d’une pile; c’est-à-dire, que les opérandes sont ajoutés en haut de la pile, et les résultats des calculs sont retournés en haut de la pile. Bien que ce concept puisse sembler inutilement compliqué au début, l’analyse d’une expression sous forme NPI a l’avantage de la concision. Sur un ordinateur, elle se prête d’ailleurs bien aux transformations en raison de sa grammaire simple.

Sommaire

Implications pratiques

  • l’ordre des opérandes est préservé. Les calculs se font de gauche à droite,
  • les opérandes précèdent l’opérateur; ils sont enlevés lorsque l’opération est évaluée.

Avantages

  • il n’y a plus de parenthèses, devenues inutiles.
  • quand une opération est faite, le résultat devient un opérande lui-même (pour les opérateurs suivants)
  • il n’y a pas d’état caché. L’utilisateur n’a pas besoin de se demander s’il frappait un opérateur ou pas : chaque frappe d’un opérateur déclenche une exécution immédiate.
  • un résultat intermédiaire peut resservir facilement. Exemple : calcul de \frac{\mathrm{sin}(\frac{3\times \pi}{4})}{\frac{3\times \pi}{4}} : ici, \frac{3\times \pi}{4} est utilisé deux fois. On peut le dupliquer dans la pile, ce qui donne : 3 [entrée] pi * 4 / DUP SIN SWAP / (ici DUP et SWAP sont des opérateurs de pile pour dupliquer et intervertir).

N.B. : sur les calculatrices HP à notation polonaise inverse, il y a également une touche « Last x », très commode, qui permet de rappeler dans le registre X de la pile (qui correspond à ce qui est affiché à l'écran) la valeur qu'il contenait avant l'application du dernier opérateur. Dans l'exemple ci-dessus, à la place de DUP SIN SWAP /, on ferait plus simplement SIN LastX / (ce qui permet de faire économiser une instruction : cela peut sembler minime, mais sur des calculatrices dont la capacité mémoire est relativement limitée, toutes les optimisations sont bonnes à prendre).

Inconvénients

  • On ne peut exécuter un opérateur que s’il est de façon univoque binaire ou unaire (alias dyadique ou monadique), c’est-à-dire opère sur deux arguments ou un. Il faut donc différencier l’opérateur binaire de soustraction (10 - 2 devient 10 2 -) de l’opérateur unaire de négation (- 2 devient 2 NEG). Plus généralement un opérateur doit prendre un nombre fixe d'arguments (il existe des opérateurs ternaires, quaternaires...) ou prendre un nombre fixe d'argument décrivant les autres arguments consommés par l'opérateur. Ainsi la fonction DROPN (HP48) consomme un premier argument dans la pile (un entier) qui lui donne le nombre des autres arguments à consommer (en l'occurrence le nombre d'éléments à retirer de la pile) ;
  • La gymnastique intellectuelle à effectuer grimpe en complexité en même temps que la taille de l’expression. Selon qu’on est habitué à la NPI ou pas, l’exercice peut paraître ludique ou contraignant.

Exemple

Le calcul :
((1 + 2) * 4) + 3
peut être noté en NPI comme ceci :
1 2 + 4 * 3 +
ou
3 4 1 2 + * +

L’expression est évaluée de la façon suivante (la pile est montrée après chaque opération) :

Entrée Opération Pile
Étape no 1 1 Pousser l’opérande 1
Étape no 2 2 Pousser l’opérande 1, 2
Étape no 3 + Addition 3
Étape no 4 4 Pousser l’opérande 3, 4
Étape no 5 * Multiplication 12
Étape no 6 3 Pousser l’opérande 12, 3
Étape no 7 + Addition 15

Le résultat final 15 se trouve en haut de la pile à la fin du calcul.

+---------------+
+             1 + [ 1 ] [ entrez ]
+               +
+               +
+---------------+

+---------------+
+             2 + [ 2 ]
+             1 +
+               +
+---------------+

+---------------+
+             3 + [ + ]
+               +
+               +
+---------------+

+---------------+
+             4 + [ 4 ]
+             3 +
+               +
+---------------+

+---------------+
+            12 +  [*] 
+               +
+               +
+---------------+

+---------------+
+             3 +  [3]
+            12 +
+               +
+---------------+

+---------------+
+            15 +  [+] 
+               +
+               +
+---------------+

Méthode pour apprendre la NPI facilement

En fait, c'est plus simple qu'il n'y paraît, le calcul : ((1 + 2) * 4) + 3 peut se lire facilement :

  • je mets 1, (1)
  • j'ajoute 2, ( 2 + )
  • je multiplie par 4, (4 *)
  • j'ajoute 3. (3 +)

ce qui donne simplement 1 2 + 4 * 3 +
La notation polonaise inverse est très intuitive, sa difficulté relève d'un manque d'habitude (la plupart des calculatrices ne l'utilisent pas). Pour traduire une expression algébrique (telle que ((1+2)*4)+3 ) il suffit de la lire en se disant ce que l'on doit faire, c'est-à-dire comprendre l'expression algébrique, faire les opérations dans le bon ordre (commencer ici par l'addition de 1 et 2).

Conversion à partir de la notation infixée

Comme l'évaluation de NPI, la conversion de la notation d'infixe en NPI est basée sur l’utilisation d’une pile. Les expressions d’infixe sont la forme de mathématique que la plupart des personnes utilisent, par exemple : 3+4 ou 3+4*(2-1).

Pour la conversion il y a 2 variables texte (chaîne de caractères), l’entrée et la sortie. Il y a également une pile pour empiler les opérateurs pas encore ajoutés à la chaîne de sortie. Pour convertir, le programme lit chaque lettre dans l’ordre et réalise l’opération liée à cette lettre.

Une conversion simple

l’entrée: 3+4
ajouter 3 à la sortie
ajouter + sur la pile des opérateurs
ajouter 4 à la sortie
à la fin de la lecture de l’entrée dépiler la pile des opérateurs dans la sortie
la sortie : 3 4 +

Ce simple exemple nous montre les règles suivantes :

  • Tous les nombres sont directement ajoutés à la sortie,
  • À la fin de la lecture de l’entrée dépiler la pile des opérateurs dans la sortie

Description de l’algorithme de conversion

  • tant qu’il y a des tokens à lire:
lire le token.
  • si c’est un nombre l’ajouter à la sortie.
  • si c'est une fonction, le mettre sur la pile.
  • si c'est un séparateur d'arguments de fonction (par exemple une virgule) :
jusqu'à ce que l'élément au sommet de la pile soit une parenthèse gauche, retirer l'élément du sommet de la pile et l'ajouter à la sortie. Si toute la pile est dépilée sans trouver de parenthèse gauche, c’est qu’il y a un mauvais parenthésage.
  • si c’est un opérateur o1 alors
1) tant qu’il y a un opérateur o2 sur le haut de la pile et si l’une des conditions suivantes est remplie.
o1 est associatif ou associatif à gauche et sa priorité est inférieure ou égale à celle d’o2, ou
o1 est associatif à droit et sa priorité est inférieure à celle d’o2,
retirer o2 de la pile pour le mettre dans la sortie
2) mettre o1 sur la pile
  • si le token est une parenthèse gauche, le mettre sur la pile.
  • si le token est une parenthèse droite, alors dépiler les opérateurs et les mettre dans la sortie jusqu’à la parenthèse gauche qui elle aussi sera dépilée, mais pas mise dans la sortie. Àprès celà, si le token au sommet de la pile est une fonction, le dépiler également pour l'ajouter à la sortie. Si toute la pile est dépilée sans trouver de parenthèse gauche c’est qu’il y a un mauvais parenthésage.
  • après la lecture du dernier token, s'il reste des éléments dans la pile il faut tous les dépiler pour les mettre dans la sortie (il ne doit y avoir que des opérateurs. Si on trouve une parenthèse gauche alors il y a eu un mauvais parenthésage).

Quelques utilisations réelles de la NPI

Voir aussi

Ce document provient de « Notation polonaise inverse ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Rpn de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • RPN — may be an acronym that refers to:*Licensed Practical Nurse, also referred to as a Registered Practical Nurse *Radio Philippines Network *Registered Parameter Number, as used in MIDI synthesizers *Registered Psychiatric Nurse *Reverse Polish… …   Wikipedia

  • RPN — ist die Abkürzung für: Reverse Polish Notation, siehe Umgekehrte Polnische Notation Repère Pierre du Niton, Höhenreferenzpunkt der Schweiz Registered Parameter Number, ein Parameter innerhalb des MIDI Standards. Diese …   Deutsch Wikipedia

  • RPN —   [Abk. für Reverse Polish Notation], umgekehrte polnische Notation …   Universal-Lexikon

  • RPN —   Sigles d’une seule lettre   Sigles de deux lettres > Sigles de trois lettres   Sigles de quatre lettres   Sigles de cinq lettres   Sigles de six lettres   Sigles de sept… …   Wikipédia en Français

  • RPN NewsCap — Format News Created by Radio Philippines Network Developed by RPN News and Current Affairs Presented by Isabel Roces …   Wikipedia

  • RPN — Reverse Polish Notation (Computing » General) * Registered Practical Nurse (Academic & Science » Libraries) * Registered Parameter Number (Computing » Networking) * Registered Professional Nurse (Business » Positions) * Rosh Pina, Israel… …   Abbreviations dictionary

  • RPN — • Reverse Polish Notation; s. UPN • Rosh Pina, Israel internationale Flughafen Kennung …   Acronyms

  • rpn — ISO 639 3 Code of Language ISO 639 2/B Code : ISO 639 2/T Code : ISO 639 1 Code : Scope : Individual Language Type : Living Language Name : Repanbitip …   Names of Languages ISO 639-3

  • RPN — [1] Reverse Polish Notation; s. UPN [2] Rosh Pina, Israel internationale Fughafen Kennung …   Acronyms von A bis Z

  • RPN — abbr. Reverse Polish Notation …   Dictionary of English abbreviation

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”