Notation polonaise inversée

ï»ż
Notation polonaise inversée

Notation polonaise inverse

Page d'aide sur l'homonymie Pour les articles homonymes, voir NPI et RPN.

La notation polonaise inverse (NPI) (en anglais RPN pour Reverse Polish Notation), Ă©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Ă© ;
  • Elle permet de voir les rĂ©sultats intermĂ©diaires et donc de dĂ©tecter plus facilement d'Ă©ventuelles erreurs.

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[rĂ©f. nĂ©cessaire].

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 (HP9100), 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 :
4 7 + 3 *
ou
3 4 7 + *
En pratique sur une calculatrice de NPI le calcul sera saisi en tant que :
« 4 Â», « entrĂ©e Â», « 7 Â», « + Â», « 3 Â», « * Â».
ou
« 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 l’opĂ©ration est Ă©valuĂ©e.

Avantages

  • il n’y a plus de parenthĂšses, 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.
  • un rĂ©sultat intermĂ©diaire peut resservir facilement. Exemple : calcul de \frac{\mathrm{sin}(\frac{3\times \pi}{4})}{\frac{3\times \pi}{4}} : ici, \frac{3\times \pi}{4} est utilisĂ© deux fois. On peut le 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).

N.B. : sur les calculatrices HP Ă  notation polonaise inverse, il y a Ă©galement une touche « Last x Â», trĂšs commode, 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 sur des calculatrices dont la capacitĂ© mĂ©moire est relativement limitĂ©e, toutes les optimisations sont bonnes Ă  prendre).

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

Exemple

Le calcul :
((1 + 2) * 4) + 3
peut ĂȘtre notĂ© en NPI comme ceci :
1 2 + 4 * 3 +
ou
3 4 1 2 + * +

L’expression est Ă©valuĂ©e de la façon suivante (la pile est montrĂ©e aprĂšs chaque opĂ©ration) :

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

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

+---------------+
+             1 + [ 1 ] [ entrez ]
+               +
+               +
+---------------+

+---------------+
+             2 + [ 2 ]
+             1 +
+               +
+---------------+

+---------------+
+             3 + [ + ]
+               +
+               +
+---------------+

+---------------+
+             4 + [ 4 ]
+             3 +
+               +
+---------------+

+---------------+
+            12 +  [*] 
+               +
+               +
+---------------+

+---------------+
+             3 +  [3]
+            12 +
+               +
+---------------+

+---------------+
+            15 +  [+] 
+               +
+               +
+---------------+

MĂ©thode pour apprendre la NPI facilement

En fait, c'est plus simple qu'il n'y paraĂźt, le calcul : ((1 + 2) * 4) + 3 peut se lire facilement :

  • 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 est trÚs intuitive, sa difficulté relÚve 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, 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 o1 alors
1) tant qu’il y a un opĂ©rateur o2 sur le haut de la pile et si l’une des conditions suivantes est remplie.
o1 est associatif ou associatif Ă  gauche et sa prioritĂ© est infĂ©rieure ou Ă©gale Ă  celle d’o2, ou
o1 est associatif Ă  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 mettre dans la sortie jusqu’à la parenthĂšse gauche qui elle aussi sera dĂ©pilĂ©e, mais pas mise dans la sortie. ÀprĂšs celĂ , 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

Voir aussi

Ce document provient de « Notation polonaise inverse ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Notation polonaise inversée de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Forth (Langage) — Pour les articles homonymes, voir Forth. Forth est un langage de programmation interactif atypique, dĂ©couvert (comme il aime Ă  le dire) par Charles H. Moore dans les annĂ©es 1960. Sommaire 1 Historique 
   WikipĂ©dia en Français

  • Forth (langage) — Pour les articles homonymes, voir Forth. Forth est un langage de programmation interactif atypique, dĂ©couvert (comme il aime Ă  le dire) par Charles H. Moore dans les annĂ©es 1960. Sommaire 1 Historique 2 
   WikipĂ©dia en Français

  • Ordre des operations — Ordre des opĂ©rations Ordre des opĂ©rations En mathĂ©matiques, la prioritĂ© des opĂ©rations ou ordre des opĂ©rations prĂ©cise l ordre dans lequel les calculs doivent ĂȘtre effectuĂ©s dans une expression complexe. Les prioritĂ©s opĂ©ratoires ainsi que les… 
   WikipĂ©dia en Français

  • Ordre des opĂ©rations — En mathĂ©matiques, la prioritĂ© des opĂ©rations ou ordre des opĂ©rations prĂ©cise l ordre dans lequel les calculs doivent ĂȘtre effectuĂ©s dans une expression complexe. Les rĂšgles de prioritĂ© sont : les calculs contenus entre parenthĂšses (ou… 
   WikipĂ©dia en Français

  • Priorite (mathematiques) — Ordre des opĂ©rations Ordre des opĂ©rations En mathĂ©matiques, la prioritĂ© des opĂ©rations ou ordre des opĂ©rations prĂ©cise l ordre dans lequel les calculs doivent ĂȘtre effectuĂ©s dans une expression complexe. Les prioritĂ©s opĂ©ratoires ainsi que les… 
   WikipĂ©dia en Français

  • PrioritĂ© (mathĂ©matiques) — Ordre des opĂ©rations Ordre des opĂ©rations En mathĂ©matiques, la prioritĂ© des opĂ©rations ou ordre des opĂ©rations prĂ©cise l ordre dans lequel les calculs doivent ĂȘtre effectuĂ©s dans une expression complexe. Les prioritĂ©s opĂ©ratoires ainsi que les… 
   WikipĂ©dia en Français

  • PrioritĂ© des opĂ©rations — Ordre des opĂ©rations Ordre des opĂ©rations En mathĂ©matiques, la prioritĂ© des opĂ©rations ou ordre des opĂ©rations prĂ©cise l ordre dans lequel les calculs doivent ĂȘtre effectuĂ©s dans une expression complexe. Les prioritĂ©s opĂ©ratoires ainsi que les… 
   WikipĂ©dia en Français

  • PrioritĂ© logique — Ordre des opĂ©rations Ordre des opĂ©rations En mathĂ©matiques, la prioritĂ© des opĂ©rations ou ordre des opĂ©rations prĂ©cise l ordre dans lequel les calculs doivent ĂȘtre effectuĂ©s dans une expression complexe. Les prioritĂ©s opĂ©ratoires ainsi que les… 
   WikipĂ©dia en Français

  • PrioritĂ© opĂ©ratoire — Ordre des opĂ©rations Ordre des opĂ©rations En mathĂ©matiques, la prioritĂ© des opĂ©rations ou ordre des opĂ©rations prĂ©cise l ordre dans lequel les calculs doivent ĂȘtre effectuĂ©s dans une expression complexe. Les prioritĂ©s opĂ©ratoires ainsi que les… 
   WikipĂ©dia en Français

  • PrĂ©cĂ©dence — Ordre des opĂ©rations Ordre des opĂ©rations En mathĂ©matiques, la prioritĂ© des opĂ©rations ou ordre des opĂ©rations prĂ©cise l ordre dans lequel les calculs doivent ĂȘtre effectuĂ©s dans une expression complexe. Les prioritĂ©s opĂ©ratoires ainsi que les… 
   WikipĂ©dia en Français


Share the article and excerpts

Direct link

 Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.