Les programmes ne sont généralement pas capables de manipuler des expressions mathématiques comme les humains les écrivent.
Il faut donc passer par une représentation interne de l'expression.
La structure la plus classique est la structure d'arbre, parce que les expressions mathématiques sont composés d'opérateurs (+, -, *, /, ...), unaires, binaires ou n-aires (cad toujours à 1, 2 ou n arguments ; exemple : l'opérateur somme, c'est le + binaire). La traduction sous forme d'arbre est donc assez naturelle (attention aux parenthèses au moment de "traduire" l'expression en l'arbre équivalent !).
Ainsi : ln(x) + 3 * 5 peut se représenter par l'arbre suivant :
*
/ \
+ 5
/ \
ln 3
/
x
Gros avantages des arbres :
- les priorités entre opérateurs s'expriment naturellement (par exemple, le fait que la multiplication s'applique toujours avant l'addition), puisque pour évaluer l'expression, on applique récursivement les opérateurs du haut de l'arbre (racine de l'arbre) jusqu'en bas (feuilles de l'arbre) ; et il n'y a plus de besoin de parenthèses
- une manipulation de l'expression revient à manipuler un noeud, puis à refaire une manipulation similaire à chaque sous-noeud. Par exemple, pour dériver l'expression ci-dessus, on commence par le noeud racine (opérateur *), et on applique la règle (u*v)' = u' * v + u * v'. Donc on fabrique une nouvelle expression avec les expressions :
+
/ \
ln 3
/
x
et
5
et leurs dérivées, que l'on calcule grâce à la récursivité.
Autre exemple, pour simplifier une expression (inévitable après une dérivation formelle), on applique des règles simples à chaque noeud de l'arbre. Exemple 0 * n'importe quel arbre = 0, 1 * n'importe quel arbre = cet arbre, 0 + n'importe quel arbre = cet arbre, n'importe quel arbre / 1 = cet arbre, etc.
