Notations infixée, préfixée, polonaise et postfixée

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Les notations infixée (ou infixe), préfixée (ou préfixe) et postfixée (ou postfixe) sont des formes d'écritures d'expressions algébriques qui se distinguent par la position relative qu'y prennent les opérateurs et leurs opérandes. Un opérateur est écrit avant ses opérandes en notation préfixée, entre ses opérandes en notation infixée et après ses opérandes en notation postfixée.

La notation infixée n'a de sens que pour les opérateurs prenant exactement deux opérandes. C'est la notation la plus courante des opérateurs binaires en mathématiques.

La notation préfixée fut inventée en 1920 par le mathématicien polonais Jan Łukasiewicz[1], c'est pourquoi elle est également appelée notation de Łukasiewicz[2], ou notation polonaise. Par analogie, la notation postfixée est appelée notation polonaise inverse. Ces deux notations permettent de se passer de parenthèses dans le case d'opérateurs d'arité fixée et connue et s'accordent à une évaluation naturelle de l'expression.

Présentation[modifier | modifier le code]

L'expression qui ajoute les nombres 1 et 2 s'écrit, en notation préfixe, « + 1 2 ». Dans les expressions infixes, les opérateurs précèdent toujours leurs opérandes qui peuvent être eux-mêmes des expressions non-triviales. Par exemple, l'expression qui serait écrite en notation infixe classique

(5 − 6) × 7

est écrite en notation infixe

× (− 5 6) 7

On notera que comme on connait l'arité des opérateurs, les parenthèses sont inutiles et l'expression précédente peut être simplifiée en

× − 5 6 7

L'évaluation du produit × est activé quand ses deux opérandes ont été évalués (à savoir, 5 moins 6, et 7). Plus généralement l'évaluation d'un opérateur d'arité n est activée après que ses n opérandes ont été évalués.

Exemples[modifier | modifier le code]

Notation préfixée[modifier | modifier le code]

Calcul des propositions de Łukasiewicz[modifier | modifier le code]

En calcul des propositions, Łukasiewicz introduisait :

pour le « non »  ;
pour l'implication  ;
pour le « ou »  ;
pour l'équivalence .

On a par exemple :

 :
 : .

Lisp[modifier | modifier le code]

Le langage de programmation Lisp utilise une notation préfixée avec parenthèses, pour autoriser les opérateurs ayant un nombre d'opérandes variable. Des parenthèses encadrent un opérateur et ses opérandes.

L’expression usuelle 3 * (4 + 5 + 6) se note en Lisp (* 3 (+ 4 5 6)).

L’expression est interprétée en remplaçant successivement une expression entre parenthèses par le résultat de l’opérateur écrit à gauche agissant sur les opérandes écrits à sa suite :

(* 3 (+ 4 5 6)) ⇒ (* 3 15) ⇒ 45.

Notation postfixée[modifier | modifier le code]

Article détaillé : Notation polonaise inverse.

Le langage Forth, de même que le PostScript et le RPL des calculatrices HP, utilisent une notation postfixée, qui de plus peut se passer de parenthèses, les opérateurs ayant un nombre fixe d’opérandes (l'addition et la multiplication ont deux opérandes, l'inverse et la racine carrée n'en ont qu'un). L’expression 3 * (4 + 5 + 6) s’écrit alors « 3 4 5 add 6 add mul ».

Lorsque l'interpréteur rencontre un opérande, il l'empile. Lorsqu'il rencontre un opérateur, il l'exécute sur les opérandes empilés et met le résultat de l'opération sur la pile. Ainsi, quand il rencontre l’opérateur add, il prend les deux nombres du haut de la pile et les remplace par leur somme. Il fait de même pour la multiplication avec l’opérateur mul. La pile aura donc successivement le contenu suivant :

(3) >> (3 4) >> (3 4 5) > add > (3 9) >> (3 9 6) > add > (3 15) > mul > (45).

Analogue en langage naturel[modifier | modifier le code]

La notation préfixée de l’expression 3 * (4 + 5 + 6) est analogue à l’expression en langage naturel : « le produit de 3 et de la somme de 4, 5 et 6 ».

L’analogue en langage naturel de la notation postfixée serait  : « prendre 4, 5 et 6 et les additionner, puis prendre 3 et le multiplier à cette somme ».

Notes et références[modifier | modifier le code]

  1. Dupas JJ, La notation polonaise, Tangente n° 120, janvier-février 2008, p30-31
  2. Philippe Flajolet et Robert Sedgewick Analytic Combinatorics, Cambridge Univerity Press, (2009), note 14, p. 75, pour qui la terminologie «notation polonaise» serait moins digne.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]