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 1924 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 cas 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éfixée, + 1 2. Dans les expressions préfixées, 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 infixée classique :

(5 − 6) × 7

est écrite en notation préfixée :

× (− 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ée quand ses deux opérandes ont été évaluées (à savoir, 5 − 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ées.

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 le « et »  ;
pour le « ou »  ;
pour l'implication  ;
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 écrites à sa suite :

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

Notation postfixée[modifier | modifier le code]

Article détaillé : Notation polonaise inverse.

Les langages de programmation Forth, PostScript et le langage RPL des calculatrices HP utilisent une notation postfixée pouvant 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'une). L'expression 3 * (4 + 5 + 6) s'écrit alors 3 4 5 add 6 add mul (ou encore 4 5 add 6 add 3 mul).

Lorsque l'interpréteur rencontre une opérande, il l'empile dans une pile. Lorsqu'il rencontre un opérateur, il dépile deux opérandes, l'applique sur elles et empile le résultat. 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.

Articles connexes[modifier | modifier le code]