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

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

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

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

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

• Langage de Łukasiewicz
• Arborescence
• Compilateur