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

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[1]. C'est la notation la plus courante des opérateurs binaires en mathématiques. Les notations préfixée et postfixée permettent de se passer de parenthèses, conduisant à une notation plus compacte. Mais se passer de parenthèse suppose que l'on connaît la signature (autrement dit l'arité de tous les opérateurs) et que cette arité est un attribut des opérateurs qui ne peut pas être modifiable[2]. La signature sert à analyser les expressions lors de leur évaluation.

La notation préfixée fut proposée en 1924 par le mathématicien polonais Jan Łukasiewicz[3],[4], c'est pourquoi elle est également appelée notation de Łukasiewicz[5], ou notation polonaise. Par analogie, la notation postfixée est appelée notation polonaise inverse. Ces deux notations (préfixée et postfixée) 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

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.

Supposons que l'on ait, de plus, une fonction ${\displaystyle f}$ d'arité 3 et trois variables ${\displaystyle x}$, ${\displaystyle y}$ et ${\displaystyle z}$. L'expression infixée ${\displaystyle f(x,f(x+y,z,z),f(x,x,y))}$ s'écrira de façon préfixée, sans parenthèses, ${\displaystyle fxf+xyzzfxxy}$. Le premier ${\displaystyle f}$ a trois arguments qui sont ${\displaystyle x}$, ${\displaystyle f+xyzz}$ et ${\displaystyle fxxy}$. Dans l'expression ${\displaystyle f+xyzz}$, on voit que ${\displaystyle f}$ a trois arguments ${\displaystyle +xy}$, puis ${\displaystyle z}$, puis ${\displaystyle z}$. L'utilisation d'une pile permet, même à un humain, d'analyser et d'évaluer ces expressions.

Exemples

Notation préfixée

Calcul des propositions de Łukasiewicz

En calcul des propositions, Łukasiewicz introduisait ^[réf. nécessaire]:

${\displaystyle N}$ pour le « non » ${\displaystyle \lnot }$ ;

${\displaystyle K}$ pour le « et » ${\displaystyle \land }$ ;

${\displaystyle A}$ pour le « ou » ${\displaystyle \lor }$ ;

${\displaystyle C}$ pour l'implication ${\displaystyle \to }$ ;

${\displaystyle E}$ pour l'équivalence ${\displaystyle \leftrightarrow }$.

Par exemple :

${\displaystyle CpAqm}$ correspond à la notation infixée ${\displaystyle p\to (q\lor m)}$

${\displaystyle ACpqm}$ correspond à la notation infixée ${\displaystyle (p\to q)\lor m}$.

Lisp

Les langages de programmation Lisp et Scheme utilisent 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 dans cette famille de langages (* 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 valeurs des opérandes écrites à sa suite :

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

Notation postfixée

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, tandis que l'expression (4 + (5 + 6)) * 3 s'écrit 4 5 6 add add 3 mul. Lorsque l'interprète rencontre un opérande, il l'empile dans une pile, pour pouvoir le dépiler de la pile plus tard. Lorsqu'il rencontre un opérateur binaire, il dépile deux opérandes, applique l'opérateur sur ceux-ci et empile le résultat. La pile aura donc successivement le contenu suivant (le signe ⇒ sépare les étapes qui se succèdent dans le temps):

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

Analogue en langage naturel

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 4 5 add 6 add 3 mul serait : « prendre 4 et 5 et les additionner, prendre le résultat et 6 et les additionner puis prendre cette somme et 3 et les multiplier ».

Langage formel des notations postfixées

Les notations postfixées (comme les notations infixées) forment un langage formel dont les mots sont composés des opérateurs et des variables[6]. On peut caractériser parmi tous les mots sur cet alphabet ceux qui correspondent à une notation préfixée. Cela se fait grâce à la notion de valence[7].

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Polish notation » (voir la liste des auteurs).

1. Quoique la notation si ... alors ... sinon ... soit aussi considérée comme une notation ternaire infixée.
2. Par exemple, un opérateur appliqué à une liste, dont l'arité dépend de la longueur de la liste, ne peut pas se passer de parenthèses ou de crochets.
3. Jan Łukasiewicz, « O znaczeniu i potrzebach logiki matematycznej », Nauka polska, vol. 10,‎ 1929, p. 604-620. C'est en 1924 qu'il en a eu l'idée, mais il ne l'a écrite qu'en 1929 !
4. Heinrich Behmann, éditeur en 1924 de l'article de Moses Schönfinkel "Über die Bausteine der mathematischen Logik", a eu, la même année et indépendamment de Łukasiewicz, l'idée d'utiliser la notation préfixeé et d'éliminer des parenthèses dans les formules de logique. Voir Moses Schönfinkel "Über die Bausteine der mathematischen Logik", Mathematische Annalen 92, p. 305-316. Traduit en français par Geneviève Vandevelde : Moses Schönfinkel, « Sur les éléments de construction de la logique mathématique », Mathématiques et sciences humaines, vol. 112,‎ 1990, p. 5-26 (lire en ligne) et traduit en anglais par Stefan Bauer-Mengelberg : "On the building blocks of mathematical logic" in Jean van Heijenoort, 1967. A Source Book in Mathematical Logic, 1879-1931. Harvard Univ. Press: 355-66. En fait, il extrapole une idée de Shönfinkel dans son séminaire de 1920, pour qui toutes les fonctions sont monadiques et les parenthèses peuvent-être éliminées dans de nombreux cas. Lire l'article logique combinatoire.
5. Philippe Flajolet et Robert Sedgewick Analytic Combinatorics, Cambridge University Press, (2009), note 14, p. 75, pour qui la terminologie «notation polonaise» serait moins digne.
6. Paul Cohn, Further Algebra and Applications, Springer Science & Business Media, 2011 (lire en ligne), p. 11 et suivante
7. Voir la proposition 1.3.1 du livre Paul Cohn, Further Algebra and Applications, Springer Science & Business Media, 2011 (lire en ligne), p. 11.

Articles connexes

• Langage de Łukasiewicz
• Arborescence
• Compilateur