[Mathématique] La notation polonaise inverse

La notation polonaise inverse
Alors… c’est quoi ce truc ?

C’est une technique pour écrire des opérations mathématiques…

Pourquoi j’en parle ?

Parce que j’ai expérimenté la chose à mon travail avec la merveilleuse librairie rrdtool et que ça m’a bien cassé les c****…

La Reverse Polish Notation en anglais consiste à écrire les opérations d’une façon non ambiguë et sans parenthèse…

Gné oO ??

Bah par exemple : 3 *4 / (1+2)
s’écrira 1 2 + 4 / 3 *
soit : 1 auquel on ajoute 2, on divise par 4 puis multiplie par 3

Au final, cette technique est bien sympa !

Je l’ai expérimenté pour des sommes de variables, je ne connaissais pas leur nombre du coup je ne savais pas combien de « + » il me fallait mais avec une ptite boucle ça a bien fonctionné !

Bon par contre je ne l’utiliserais pas tous les jours :p

Plus d’infos grâce à mon ami Wikipedia :

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

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 + × ».

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

• l’ordre des opérandes est préservé
• les calculs se font en lisant l’expression de gauche à droite
• les opérandes précèdent l’opérateur et l’expression qui décrit chaque opérande disparaît lorsque l’opération est évaluée, pour être remplacée par la valeur calculée

Avantages

La NPI présente les avantages suivants :

• l’écriture est raccourcie grâce à la suppression des parenthèses
• un résultat intermédiaire peut être réutilisé.
  Par exemple dans le calcul de on voit rapidement que l’expression est utilisée deux fois.
  On peut la dupliquer dans la pile, ce qui donne :
  3 [entrée] pi * 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)

Avec un peu d’habitude, l’utilisateur effectue plus rapidement ses calculs sur une calculatrice en NPI que sur une calculatrice à notation infixée.

Inconvénients

• 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
• 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 + (en notation infixée respectivement a + b = b + a.
• L’associativité de l’addition implique que : a b c + + = a b + c + (en notation infixée respectivement a + (b + c) = (a + b) + c.
• La distributivité implique que : a b + c * = a c * b c * + (en notation infixée respectivement (a + b) * c = a * c + b * c ou bien c * (a + b)).

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 », « + », « × », « + »
(on observe que la première séquence nécessite moins de pressions de touches !)

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ément 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) :

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

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 +

• 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, HP-12c, etc.
• Le système d’exploitation Omega pour la calculatrice NumWorks, fork du système d’exploitation officiel.
• 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 pour LaTeX et BibTex .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)
• La plupart des consoles d’éclairage professionnelles (jeux d’orgues numériques), destinées à la programmation des effets lumineux dans le monde du spectacle.
• La création de graphiques complexes dans rrdtools
• Le langage WarpScript, créé par Warp10 pour faciliter le traitement des Géo-Time Series (GTS)

Ah oui et pour ceux/celles qui se demanderaient ce qu’est la merveilleuse librairie RRDTool, voici plus d’infos…
Hum quand je dis librairie c’est pas un endroit où on achète des bouquins, c’est un ensemble d’outils pour créer des graphs.
De base ça permet de créer des fichiers qui ont une taille fixe et qui ne grossiront pas avec le temps, une sorte de base de données en somme !
Vous vous demandez comment un fichier qui se rempli au fur et à mesure ne peut pas grandir ?? et bien c’est parce qu’on peut mettre en place des sortes de moyenne, genre on garde toutes les données sur une semaine puis entre une semaine et 1 mois on va stocker les max sur une heure, puis entre 2 mois et un an on va stocker les max sur une semaine etc etc !
Ah oui je ne sais pas si vous le savez mais dans la vraie vie je suis développeuse python dans une équipe qui crée des outils de supervision et du coup j’utilise ce genre d’outils pour générer des petits graphs 🙂
Bon j’avoue que visuellement les graphs sont un peu vieillots, maintenant j’essaie d’utiliser des librairies en javascript mais pour les trucs « historiques » ça reste encore fait grace à RRDTool !

La librairie RRDTool s’utilise avec plusieurs langages de programmation, j’ai testé en perl et en python !

Bon sinon la définition de wikipedia :

RRDtool est un outil de gestion de base de données RRD (Round-Robin database) créé par Tobias Oetiker. Il est utilisé par de nombreux outils open source, tels que Cacti, collectd, Lighttpd, et Nagios, pour la sauvegarde de données cycliques et le tracé de graphiques, de données chronologiques. Cet outil a été créé pour superviser des données serveur, telles la bande passante et la température d’un processeur.
Le principal avantage d’une base RRD est sa taille fixe.

RRDTool inclut également un outil permettant de représenter graphiquement les données contenues dans la base.

RRDTool est un logiciel libre distribué selon les termes de la GNU GPL.

Un exemple de graph :