Notation polonaise inverse

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Notation post-fixée)
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir NPI et RPN.
Article général Pour un article plus général, voir Notations infixée, préfixée, polonaise et postfixée.
Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Cet article ou une de ses sections doit être recyclé (30 août 2016).

Une réorganisation et une clarification du contenu paraissent nécessaires. Discutez des points à améliorer en page de discussion ou précisez les sections à recycler en utilisant {{section à recycler}}.

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 1920 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, l’expression « 3 × (4 + 7) » peut s'écrire en NPI sous la forme « 4 {Ent}[1] 7 + 3 × », ou encore sous la forme « 3 {Ent} 4 {Ent} 7 + × ».

Histoire[modifier | modifier le code]

Dérivée de la notation polonaise présentée en 1920 par le mathématicien polonais Jan Łukasiewicz[2] , la NPI a été inventée par le philosophe et informaticien australien Charles Leonard Hamblin (en) dans le milieu des années 1950, pour permettre les calculs sans faire référence à une quelconque adresse mémoire[3].

À la fin des années 1960, 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[2].

Réalisation[modifier | modifier le code]

Exemple d'utilisation de la pile en RPN

Les calculatrices NPI sont fondées sur l’utilisation d’une pile, en d'autres termes les opérandes sont disposés au sommet de la pile, tandis que les résultats des calculs sont retournés aussi au sommet de la pile. Bien que ce concept puisse dérouter le débutant, la présentation d’une expression en notation polonaise inversée a l’avantage de la concision.

Implications pratiques[modifier | modifier le code]

Cette technique a plusieurs avantages :

  • l’ordre des opérandes est préservé ;
  • les calculs se font en lisant l'expression de gauche à droite ;
  • les opérandes précèdent l’opérateur et l'expression qui décrit chaque opérande disparaît lorsque l'opération est évaluée, pour être remplacée par la valeur calculée.

Avantages[modifier | modifier le code]

La NPI présente les avantages suivants :

  • 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 on voit rapidement que l'expression est utilisée deux fois. On peut la dupliquer dans la pile, ce qui donne :
    • 3 [entrée] pi * 4 / DUP SIN SWAP / 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.
  • elle permet de voir les résultats intermédiaires et donc de détecter plus facilement d'éventuelles erreurs[pourquoi ?] ; à l’époque des premiers circuits intégrés, cela en diminuait la complexité (gestion d'une pile et d'opérateurs de pile).

Avec un peu d'habitude, l'utilisateur effectue plus rapidement ses calculs sur une calculatrice en NPI que sur une calculatrice à notation infixée.

Inconvénients[modifier | modifier le code]

Les principaux inconvénients sont :

  • il faut un séparateur entre deux opérandes successifs[pas clair] ;
  • on ne peut exécuter un opérateur que s’il est de façon univoque binaire ou unaire, 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.[réf. nécessaire] Selon qu’on est habitué à la NPI ou pas, l’exercice peut paraître ludique ou contraignant.

Propriétés[modifier | modifier le code]

  • La commutativité de l'addition implique que : a b + = b a +
  • L'associativité de l'addition implique que : a b c + + = a b + c + = a + b + c
  • La distributivité implique que : a b + c * = a c * b c * +

Exemple[modifier | modifier le code]

Le calcul :

((1 + 2) × 4) + 3

peut être noté en NPI

1 2 + 4 × 3 +

ou

3 4 1 2 + × +

En pratique sur une calculatrice à NPI le calcul sera saisi en tant que :

« 1 », « entrée » ou « espace », « 2 », « + », « 4 », « × », « 3 », « + »

ou

« 3 »,« entrée » ou « espace », « 4 », « entrée » ou « espace », « 1 », « entrée » ou « espace », « 2 », « + », « × », « + »
(on observe que la première séquence nécessite moins de pressions de touches !)

L’expression est évaluée de la façon suivante (la pile est montrée après chaque opération. Elle est représentée dans le sens physique, ie. le dernier élément de la pile en haut, bien que de nombreuses calculatrices placent l'élément le plus récent en bas pour des raisons d'ergonomie) :

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

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

Méthode pour apprendre la NPI facilement[modifier | modifier le code]

La notation polonaise inverse peut être vue comme intuitive, sa difficulté relevant essentiellement d'un manque d'habitude (la plupart des calculatrices non HP 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, puis multiplier par 4 etc..).

Le calcul ((1 + 2) × 4) + 3 peut se lire intuitivement :

  • 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 +

Quelques utilisations réelles de la NPI[modifier | modifier le code]

  • Le langage de programmation Forth
  • Le langage de programmation RPL (Hewlett Packard)
  • Les calculatrices scientifiques Hewlett-Packard, dont les HP-35, HP-41, HP-28, HP-48, HP-15C, HP-35s, HP-12c,...
  • Le langage de description de pages PostScript
  • Le programme calc[4], intégré dans Emacs
  • Le tableur d’Unix, le programme dc
  • L’écriture d’interprètes
  • Le langage de description de format de bibliographie Latex .bst
  • dans les vols spatiaux, où elle présente un gain de temps non négligeable ainsi qu'un risque moindre d'erreur (pas de risque de parenthèse manquante ou décalée)
  • le module MODET, utilisé dans le langage de programmation de traitement sismique Geovecteur (ainsi que dans la version plus récente, Geocluster)

Notes et références[modifier | modifier le code]

  1. Enter
  2. a et b (en) What is RPN?, sur le site hpmuseum.org, consulté le 19 mai 2013
  3. (en) Biographie de C.L.Hanblin, sur le site vukutu
  4. calc, sur le site gnu.org

Articles connexes[modifier | modifier le code]