Notation polonaise inverse

Exemple d'utilisation de la pile en RPN

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

Par exemple, sur une calculatrice, l’expression $3\times (10+5)$ peut s'écrire en NPI sous la forme Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche, ou encore sous la forme Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche.

Histoire

Friden EC-132, premier calculateur à utiliser la NPI.

Dérivée de la notation polonaise utilisée pour la première fois en 1924 par le mathématicien polonais Jan Łukasiewicz, la NPI a été inventée par le philosophe et informaticien australien Modèle:Lien dans le milieu des années 1950, pour permettre les calculs sans faire référence à une quelconque adresse mémoire.

Un des premiers ordinateurs conçu, le Zuse 4 utilisait une pile, et une arithmétique de type NPI dès 1945, avant même que le concept soit formalisé. Puis d'autres ordinateurs comme le English Electric KDF9 ou le Burroughs B5000 en ont appliqué le principe dès 1963.

Mais la NPI se développera réellement sur les calculatrices, comme moyen de saisie interactif d'expression arithmétiques. Le premier calculateur électronique utilisant cette notation est la Modèle:Lien EC-132 en 1964Modèle:,.

C'est à la fin des années 1960, qu'elle a été diffusée dans le public comme interface utilisateur avec les calculatrices de bureau de Hewlett-Packard (HP-9100), puis avec la calculatrice scientifique HP-35 en 1972.

Implications pratiques

• l’écriture est raccourcie grâce à la suppression des parenthèses ;
• un résultat intermédiaire peut être réutilisé. Par exemple dans le calcul de $\frac{\mathrm{s}\mathrm{i}\mathrm{n}(\frac{3\times \pi }{4})}{\frac{3\times \pi }{4}}$ on voit rapidement que l'expression $\frac{3\times \pi }{4}$ est utilisée deux fois. On peut la dupliquer dans la pile, ce qui donne :
  • Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche Modèle:Touche avec DUP et SWAP des opérateurs de pile pour dupliquer et intervertir.
• les calculs intermédiaires sont gérés sous forme de pile.
• parce qu'elle permet de voir les résultats intermédiaires, elle permet de détecter plus facilement les erreurs et donc un débogage plus rapide ; à l’époque des premiers circuits intégrés, cela en diminuait la complexité (gestion d'une pile et d'opérateurs de pile).
• ni l'opérateur, ni les parenthèses ne servant de séparateur, il faut en fournir entre deux opérandes successifs. Une espace devrait pouvoir suffire dans la majorité des cas ; sur une calculatrice, il s'agit de la touche Modèle:Touche.

Quelques utilisations réelles de la NPI

Fichier:Typing the calculation for "8 times 6" into a pocket calculator HP-32SII which uses RPN logic.webm

• Le langage de programmation Forth
• Le langage de programmation RPL (Hewlett Packard)
• Le langage de programmation RPL/2
• Les calculatrices scientifiques Hewlett-Packard, dont les HP-35, HP-41, HP-28, HP-48, HP-15C, HP-35s, HP-12c, etc.
• Le langage de description de pages PostScript
• Le programme calc, intégré dans Emacs
• Le tableur d’Unix, le programme dc
• L’écriture d’interprètesModèle:Référence nécessaire
• Le langage de description de format de bibliographie pour LaTeX et BibTex .bstModèle:,.
• La création de graphiques complexes dans rrdtools.
• Le langage WarpScript, créé par Warp10 pour faciliter le traitement des Géo-Time Series (GTS).

Annexes

Articles connexes

• Pile (informatique)
• Langue SVO
• Langue SOV
• Notations infixée, préfixée, polonaise et postfixée
• Algorithme Shunting-yard

Liens externes

• "ENTER" de Jean-Daniel Dodin, livre en français pour apprendre la NPI