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.
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.
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és en NPI comme ceci:
- 1 2 + 4 * 3 +
L'expression est évalués de la façon suivante (la pile est montré après avec 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éslutat 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
Comme l'évaluation de NPI, la conversion de la notation d'infixe en NPI est basé 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é à 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 nombre 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
- 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 suivante est remplie.
-
-
- o1 est associativité à gauche et sa priorité est inférieur ou égal à 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
- 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épillée, mais pas mise dans la sortie. Si toute la pile est dépile 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 utilisation réelles de la NPI
Voir aussi
Référence
Page d'accueil
encyclopedie-enligne.com en page d'accueil