Notation polonaise inverse
la notation polonaise inverse (NPI), é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é.
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 (à vérifier).
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, 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 :
- 3 4 7 + *
- En pratique sur une calculatrice de NPI le calcul sera saisi en tant que :
- « 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 que l’opération est évaluée.
Avantages
- il n’y a plus de parenthèse, 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.
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).
- la gymnastique intellectuelle à effectuer grimpe en complexité en même temps que la taille de l’équation. 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 +
L’expression est évaluée de la façon suivante (la pile est montrée après chaque opération) :
- Entrée Pile Opération
- 1 1 Pousser l’opérande
- 2 1,2 Pousser l’opérande
- + 3 Addition
- 4 3,4 Pousser l’opérande
- * 12 Multiplication
- 3 12,3 Pousser l’opérande
- + 15 Addition
Le résultat final 15 se trouve en haut de la pile à la fin du calcul.
+---------------+ + 1 + [ 1 ] [ entrez ] + + + + +---------------+ +---------------+ + 2 + [ 2 ] [ entrez ] + 1 + + + +---------------+ +---------------+ + 3 + [ + ] + + + + +---------------+ +---------------+ + 4 + [ 4 ] [ entrez ] + 3 + + + +---------------+ +---------------+ + 12 + [*] + + + + +---------------+ +---------------+ + 3 + [3] [entrez ] + 12 + + + +---------------+ +---------------+ + 15 + [+] + + + + +---------------+
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
- tant qu’il y a des tokens à lire:
- lire le token
- si c’est un nombre l’ajouter à la sortie
- si c’est un opérateur o1 alors
- 1) s’il y a un opérateur o2 sur le haut de la pile et si l’une des conditions suivantes est remplie.
- o1 est associativité à gauche et sa priorité est inférieure ou égale à celle d’o2, ou
- o1 est associativité à 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
- 1) s’il y a un opérateur o2 sur le haut de la pile et si l’une des conditions suivantes est remplie.
- 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 mettant dans la sortie jusqu’à la parenthèse gauche qui elle aussi sera dépilée, mais pas mise dans la sortie. Si toute la pile est dépilée sans touver de parenthèse gauche c’est qu’il y a un mauvais parenthésage.
- après la lecture du dernier token il faut dépiler tous les opérateurs de la pile et mettre chaque élément dans la sortie.
S’il y a une parenthèse gauche c’est qu’il y a eu un mauvais parenthésage.
Quelques utilisations réelles de la NPI
- Le langage de programmation Forth
- Hewlett-Packard les calculatrices scientifiques
- PostScript
- TI-68k (Ti-89) implémentation
- Le tableur d’Unix, le programme dc
- l’écriture d’interpréteur
Voir aussi
- pile (informatique)
- sujet objet verbe
- sujet verbe objet
- infixe le