Arbres II

1. * On cherche à manipuler des expressions numériques écrites en notation préfixe. Pour cela, on représente ces expressions par des arbres. Par exemple, la commande
   java tp08_ex4 ADD MUL 4 NEG 3 SUB 4 2
   commence par construire l'arbre suivant.

       .__ADD___.
       |        |
    ._MUL_.  ._SUB_.
    |     |  |     |
    4  ._NEG 4     2
       |
       3
   

   Dans le fichier tp08_arbre.java (pour télécharger, cliquer ici) est définie la classe ArbreExpression.

   class ArbreExpression {
     final static int fun_add=0;
     final static int fun_sub=1;
     final static int fun_mul=2;
     final static int fun_div=3;
     final static int fun_neg=4;
     final static String[] fun={"ADD","SUB","MUL","DIV","NEG"};
     final static String[] fun_dsp={"+","-","*","/","-"};
     final static int[] arite={2,2,2,2,1};
   
     boolean typeFonction;
     int val;
     ArbreExpression g,d;
   
     ArbreExpression(boolean type_expr,int val_expr,
         ArbreExpression gauche,ArbreExpression droite) {...}
     public String toString() {...}
   }
   

   On considère un objet a de type ArbreExpression. Lorsque le booléen a.typeFonction vaut false, l'arbre est réduit à une feuille de type entier et de valeur a.val. Dans le cas contraire, l'arbre représente une fonction de type défini par a.val. Ce type de fonction est en fait un entier qui doit être égal à l'une des constantes prédéfinies suivantes.
   • ArbreExpression.fun_add: on a une addition (ADD)
   • ArbreExpression.fun_sub: on a une soustraction (SUB)
   • ArbreExpression.fun_mul: on a une multiplication (MUL)
   • ArbreExpression.fun_div: on a une division (DIV)
   • ArbreExpression.fun_neg: on a un changement de signe (NEG)
   La constante ArbreExpression.arite[a.val] représente le nombre d'arguments (0, 1 ou 2) de la fonction. S'il n'y a qu'un argument, c'est a.g, sinon, c'est a.g et a.d. D'autres constantes sont prédéfinies, notamment ArbreExpression.fun[i] qui donne la chaîne qui représente la fonction de type i, et ArbreExpression.fun_dsp[i] qui est utilisée pour un affichage plus algébrique.

   Compléter le fichier tp08_ex1tmplt.java (pour télécharger, cliquer ici). Ce fichier fournit une méthode

   static ArbreExpression creeExpression(String[] argv) throws PasComprisException
   qui prend une chaîne argv qui contient l'expression préfixe et retourne l'expression sous forme d'arbre. Si la chaîne admet une syntaxe incorrecte, l'exception PasComprisException est émise. L'exercice consiste à définir les méthodes suivantes.
   1. static int evalExpression(ArbreExpression a)
      qui évalue la valeur numérique de l'expression a en retournant cette valeur. Dans l'exemple précédent, la méthode retourne -10.
   2. static String algebrique(ArbreExpression a)
      qui retourne sous forme de chaîne la forme algébrique d'une expression. Dans l'exemple précédent, la méthode retourne
      "((4)*(-(3)))+((4)-(2))"
   
   [corrigé]

2. ** On reprend l'exercice précédent en ajoutant des fonctions d'arité 0: une variable x et des constantes a, b et c. Ecrire une méthode
   static ArbreExpression deriveExpression(ArbreExpression a)
   qui dérive une expression par rapport à la variable x. Ecrire une méthode
   static ArbreExpression simplifieExpression(ArbreExpression a)
   qui simplifie une expression: les sous-expressions qui n'ont pas d'occurrence en x, a, b ou c seront évaluées, les additions à zéro seront simplifiées, ainsi que les multiplications par zéro ou un.
   [corrigé]

3. *** On utilise la structure d'abre AVL pour des arbres binaires de recherche (voir le TD7). Refaire l'exercice 1 du TD7 (insertion) avec cette structure de données.
   Indication: faire les méthodes suivantes:
   1. static Arbre rotationDroite(Arbre a)
   2. static Arbre rotationGauche(Arbre a)
   3. static Arbre insere(int v,Arbre a,int[] diff)
      où diff est un tableau a un élément diff[0]qui vaut la différence entre la profondeur après et avant l'insertion. (Valeur retournée par la méthode de manière détournée.)
   
   [corrigé]