Expressions arithmétiques

Une expression arithmérique totalement parenthésée (EATP) se définit de la sorte,

• Base Tout nombre $x \in \mbox{I\hspace{-.15em}R}$ est une EATP.
• Induction Soit $E, E^\prime$ deux EATPs, alors $(E + E^\prime)$, $(E - E^\prime)$, $(E \times E^\prime)$ et $(E / E^\prime)$ sont des EATPs.

Une juxtaposition de symboles $X$ est une EATP s'il est possible de générer $X$ en applicant un nombre fini de fois les règles précédentes. Si l'on souhaite définir formellement une EATP, il convient de les représenter de façon ensembliste. On redéfinit donc l'ensemble $\mathcal{E}$ des EATPs de la sorte :

• Base $\mbox{I\hspace{-.15em}R}\subset \mathcal{E}$
• Induction $\forall E, E^\prime \in \mathcal{E}$, $+(E, E^\prime), -(E, E^\prime), \times (E, E^\prime), /(E, E^\prime) \in \mathcal{E}$.

Cette définition met en correspondance des expressions comme $(3 + (4 \times 5))$ avec des ensembles de la forme $+(3, \times(4, 5))$, plus faciles à manier dans des algorithmes. Naturellement, on représentera toute expression arithmérique par un arbre binaire. Les feuilles représenteront les atomes de nos expressions et les noeuds représenteront les règles.