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, et sans que la priorité des opérateurs n'intervienne. 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.

Cette notation est très utilisée en informatique. Elle permet de calculer les opérations à l'aide d'une structure pile.

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

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

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 Friden (en) EC-132 en 1964.

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.

Mise en pratique

Transformation d'une expression avec parenthèses vers une expression utilisant la notation polonaise inverse

Pour transformer une expression avec parenthèses en notation polonaise inverse, on regarde quelle est l'opération prioritaire, et on place ses deux opérandes puis son opérateur de gauche à droite, et on continue jusqu'à avoir traité toutes les opérations du problème.

Prenons par exemple l'expression $(4*(1+2))-3$. Son opération prioritaire est $1+2$. On commence donc notre notation polonaise inverse sous la forme $1\ 2\ +$. Vient ensuite l'opération multiplication, avec pour opérande $4$ et $(1+2)$. Notre notation polonaise devient $4\ 1\ 2\ +\ *$. Enfin, on peut traiter l'opération $-$, qui a pour opérande $3$ et $4*(1+2))$. La notation polonaise inverse de l'expression est donc $4\ 1\ 2\ +*\ 3\ -$.

De manière plus formelle, l'algorithme de Shunting-Yard peut être utilisé.

Calcul d'une expression exprimée sous la forme notation polonaise inverse

En lisant de gauche à droite, on avance jusqu'au premier opérateur rencontré. On effectue alors son opération sur les deux nombres précédant l'opération. Le résultat remplace alors les trois éléments précédents dans la notation. On continue jusqu'à obtenir un seul nombre, le résultat final.

Prenons par exemple l'expression $4*(1+2))-3$, qui s'écrit sous la forme $4\ 1\ 2+*\ 3\ -$ en notation polonaise inversée. Le premier opérateur est $+$, les deux nombres le précédent sont $1$ et $2$ : on obtient donc $4\ (1+2)*3\ -$, c'est-à-dire $4\ 3*3\ -$. Dans cette nouvelle expression, le premier opérateur est $*$, et les deux nombres le précédent sont $4$ et $3$ : on obtient $1\ 2\ 3\ -$. Enfin, dans cette nouvelle expression, le premier opérateur est $-$, et on obtient $12-3$, soit $9$.

En informatique

En informatique, cette notation permet de traiter les expressions mathématiques à l'aide de la pile. Voici une implémentation en pseudo-code permettant de calculer le résultat d'une expression écrite en notation polonaise inverse :

int i;
int n = longueur(expression)
pile P

Pour i allant de 0 à (n-1)
{
    Si expression[i] != operateur
    P.push(expression[i])
    Sinon
    {
        a = P.pop()
        b = P.pop()
        c = operation(a, b)
        P.push(c)
    }
}
return (P.pop())

Implications pratiques

• l’écriture est raccourcie grâce à la suppression des parenthèses, et l'ordre dans lequel les opérations sont réalisés ne dépend que de leur place dans cette notation, et non plus de leurs opérateurs ;
• un résultat intermédiaire peut être réutilisé. 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 Enter π * 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.
• 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 Enter.

Quelques utilisations réelles de la NPI

Vidéo montrant la séquence de touches pour calculer huit fois six sur une calculatrice HP-32SII

• 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ètes^{[réf. nécessaire]}
• Le langage de description de format de bibliographie pour LaTeX et BibTex .bst.
• La création de graphiques complexes dans rrdtools.
• Le langage WarpScript, créé par Warp10 pour faciliter le traitement des Géo-Time Series (GTS).

Dans le domaines de processeurs

En 1963, le processeur B5000 de Burroughs suivait la structure de la notation polonaise inversée au niveau de son architecture. Cependant, cette pratique ne s'est pas développée. Notamment dans le domaine des microprocesseurs, cette structure a été abandonnée car son utilisation avec les registres n'était pas efficace.

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

• Notice dans un dictionnaire ou une encyclopédie généraliste :

  • Den Store Danske Encyklopædi