Notation polonaise inverse

La notation polonaise inverse (NPI), é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} 7 + 3 × », ou encore sous la forme « 3 {Ent} 4 {Ent} 7 + × ».

Histoire

Dérivée de la notation polonaise présentée en 1920 par le mathématicien polonais Jan Łukasiewicz , 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.

À 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.

Réalisation

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.

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

La NPI présente les avantages suivants :

• Simplification de l’écriture grâce a la suppression des parenthèses, devenues inutiles.
• Quand une opération est effectuée, le résultat devient un opérande lui-même (pouvant être mémorisé ou utilisé par 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 (ou une mémorisation) immédiate.
• Un résultat intermédiaire peut resservir facilement. Par exemple dans le calcul de ${\frac {\mathrm {sin} ({\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 : 3 [entrée] pi * 4 / DUP SIN SWAP / (ici DUP et SWAP sont des opérateurs de pile pour dupliquer et intervertir).
• On peut gérer ces calculs intermédiaires sous forme de pile (en anglais stack ou LIFO pour last in, first out). Le passage par la NPI permet donc d’organiser plus facilement le travail d’optimisation du compilateur.
• Elle permet de voir les résultats intermédiaires et donc de détecter plus facilement d'éventuelles erreurs.
• à l’époque des premiers circuits intégrés, cela en diminuait aussi la complexité (gestion d'une pile et d'opérateurs de pile).

Au total, avec un peu d'habitude, l'utilisateur effectue plus rapidement ses calculs sur une calculatrice en NPI que sur une calculatrice ordinaire.

N.B. : certaines calculatrices HP à notation polonaise inverse comportent une touche « Last x », 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 peut être essentiel, sur des calculatrices dont la capacité mémoire est relativement limitée).

Inconvénients

• Il faut un séparateur entre deux opérandes successifs.

• 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. Selon qu’on est habitué à la NPI ou pas, l’exercice peut paraître ludique ou contraignant.

Propriétés

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

Exemple

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 », « + », « × », « + »

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éments 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

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 +

La notation polonaise inverse peut être vue comme intuitive, sa difficulté relevant essentiellement 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 habituellement comme, 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 o₁ alors

1) tant qu’il y a un opérateur o₂ sur le haut de la pile et si l’une des conditions suivantes est remplie.

o₁ est associatif ou associatif à gauche et sa priorité est inférieure ou égale à celle d’o₂, ou

o₁ est associatif à droite et sa priorité est inférieure à celle d’o₂,

retirer o₂ de la pile pour le mettre dans la sortie

2) mettre o₁ 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. Après cela, 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

• 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...
• 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è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)

Articles connexes

• Pile (informatique)
• Langue SVO
• Langue SOV
• Notations infixée, préfixée, polonaise et postfixée
• Arborescence