TD d'informatique No. 6 : arbres et expressions

Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr

Lundi 18 décembre 1999

1   Utilisation des arbres pour représenter des expressions arithmétiques

On peut utiliser les arbres pour représenter les expressions arithmétiques. Pour représenter un nombre, on met ce nombre comme attribut d'une feuille. Pour représenter une opération unaire (par exemple sin ou cos), on crée un noeud qui a cet opérateur comme attribut et qui a un fils qui contient, sous forme d'arbre, l'expression qui est son argument. Pour représenter une expression avec un opérateur binaire comme a + b, on crée un noeud qui contient + et qui a deux fils qui contiennent respectivement a et b. Pour rendre les choses plus visuelles, la figure 1 montre l'arbre qui correspond à l'expression : 2 cos p + q/2 sin p - q/2

Figure 1: Un arbre.

Le but du TD est de construire de tels arbres pour les opérations suivantes : +, -, *, /, ^, sin et cos, avec les nombres réels. Pour entrer au clavier une expression, on peut penser à trois moyens.
Ordre infixe :
pour les opérations binaires, on entre un opérande, l'opérateur et le deuxième opérande. Cette façon de faire mène à des ambiguïtés qu'il faut lever par l'emploi de parenthèses, aussi n'utiliserons-nous pas ceci dans le présent TD. Par exemple, l'interprétation de 2 * 3 + 4 est ambigüe.
Ordre préfixe :
dans cet ordre, on entre d'abord l'opérateur, puis ses opérandes ensuite. Cet ordre n'est pas ambigu. Pour l'expression déjà donnée, cela donne : * 2 * cos / + p q 2 sin /- p q 2.
Ordre postfixe :
dans ce dernier cas, l'opérateur vient après ses opérandes. Par exemple : 2 p q + 2 / cos p q - 2 / sin * *

2   Travail demandé

Écrire 3 fonctions. Les deux premières peuvent être écrites dans l'ordre que vous voulez. N'écrivez la troisième qu'ensuite.

Principe pour les entrées /sorties.
Il est fourni quelques fonctions pour faciliter les entrées sur la page web. La fonction Lire_ligne sert à lire une ligne de texte. On l'utilise une fois pour chaque expression, en début du programme principal. On pourra, en s'inspirant de Lire_Premier_Mot, écrire une fonction Mot_Suivant qui sert à récupérer les mots qui forment la ligne qui a été lue par Lire_Ligne. Par exemple, si à l'appel de Lire_Ligne, l'utilisateur répond + 2 3, le premier appel à Mot_Suivant renvoie la chaîne "+", le deuxième appel la chaîne "2", et le troisième la chaîne "3".

2.1   Première fonction : lecture d'une expression préfixe

La première fonction suppose que la ligne lue par Lire_Ligne est une expression écrite en ordre préfixe. Cette fonction renvoie l'arbre correspondant à cette expression. (Indication : faire une fonction récursive.)

2.2   Deuxième fonction : calcul de l'expression représentée par un arbre

Cette deuxième fonction reçoit un arbre en argument, et renvoie le réel qui est le résultat de l'évaluation de l'expression représentée par l'arbre. (Indication : faire une fonction récursive.)

2.3   Troisième fonction : lecture d'une expression postfixe

La difficulté avec les expressions postfixes vient du fait que les opérateurs peuvent venir longtemps après leurs opérandes (par exemple, le premier 2 de l'expression est un opérande de la dernière multiplication. On crée donc une pile où l'on va stocker les opérandes en attente d'utilisation.

La fonction ne doit pas être récursive. Tant qu'il y a des mots, elle les lit. Pour chacun d'entre eux, elle crée le noeud correspondant, va chercher dans la pile les opérandes éventuels et empile le noeud construit.

À la fin, elle renvoie l'arbre se trouvant en sommet de pile.

3   Pour aller plus loin

On peut se servir des mêmes arbres pour stocker des expressions contenant des variables et pas seulement des nombres. Modifiez les programmes pour construire de tels arbres, et écrivez une fonction qui prend un tel arbre en argument et calcule sa dérivée par rapport à une variable donnée.

Bonne fin d'année et bonnes vacances !
This document was translated from LATEX by HEVEA.