Les arbres binaires permettent de représenter de manière simple et efficace les expressions arithmétiques telles que (2+3)-5. Une expression peut contenir des doubles et des opérations mathématiques. Pour ce TD, les opérations que nous utiliserons seront *, /, + et -.

L’expression arithmétique

 (((5.0 * 5.0) + (8.0/2.0)) + 4.0) 

peut être représentée comme suit :

Remarquons que les feuilles de l’arbre contiennent les valeurs (doubles), tandis que les noeuds internes contiennent les operateurs.

• lire et utiliser les arguments donnés sur la ligne de commandes (donc, comprendre public static void main(String[] args) en détails);
• aborder le mécanisme d’interfaces de Java;
• construire des arbres binaires et les parcourir.

Il est important que vous respectiez les règles suivantes :

• nommer les classes, variables et méthodes EXACTEMENT comme demandé dans l’énoncé
• écrire chaque classe java dans un fichier à part qui porte le nom de la classe (suivi de .java).
• coder de manière claire et organisée de sorte que votre code soit aisément lisible par un tiers. Des commentaires pertinents seront appréciés.

Rappelons que les éléments d’un arbre binaire représentant une expression arithmétique peuvent être de 2 types :

• noeud interne, représentant alors une opération arithmétique (+, -, *, /), et ayant un sous-arbre gauche et un sous-arbre droit
• feuille (noeud terminal), représentant alors une valeur (double), dont les sous-arbres gauche et droit sont null.

Ecrire la classe BinaryTree, qui doit implémenter l’interface TreeElem, et avoir:

• un attribut oper de type char
• un attribut valeur de type double
• deux références respectivement à un sous-arbre gauche (left) et à un sous-arbre droit (right) qui sont tous les deux de type BinaryTree.

REMARQUE : vous allez utiliser le type TreeElem pour résoudre les exercices qui suivent, seulement pour l’implémentation des méthodes spécifiées dans la déclaration de l’interface. La déclaration de l’interface et l’utilisation de implements TreeElem pour l’implémentation de BinaryTree servent à permettre au code d’affichage graphique des arbres d’avoir une représentation textuelle du contenu de l’arbre (l’étiquette) et de parcourir l’arbre.

La classe BinaryTree doit avoir 2 constructeurs :

• BinaryTree(double valeur), à utiliser lorsque l’élément représente une valeur, c-à-d lorsque c’est un noeud terminal.
• BinaryTree(char oper, BinaryTree left, BinaryTree right), à utiliser lorsque l’élement de l’arbre contient un opérateur (noeud interne).

Téléchargez le fichier TreeDraw.java, contenant une petite classe Java servant à afficher graphiquement une représentation de tout arbre binaire. Cette classe utiliser l’interface TreeElem pour accéder aux méthodes de l’ une ou l’autre des deux classes implémentées.

Le code suivant permet de tester le constructeur et l’affichage:

 public static void main (String[] args){
	BinaryTree l = new BinaryTree('-', new BinaryTree(5.0),new BinaryTree(2.0));
	BinaryTree r = new BinaryTree(3.0);
	BinaryTree t = new BinaryTree('+',l,r);		
	TreeDraw.drawTree(t);
}	

Vous devriez obtenir le résultat suivant :

Déposez votre implémentation de BinaryTree.java ici:

Nous avons déjà vu en amphithéâtre (http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/05/cours.html#slide:41) comment évaluer une expressions arithmétiques representer par un arbre binaire.

Ajouter à la classe BinaryTree la méthode suivante :

double evaluate()

La méthode doit parcourir l’arbre dans un ordre approprié, et evaluer l’expression arithmetique.

Vous pouvez tester votre implémentation en ajoutant a la fin du public static void main(String[] args) la ligne suivante :

  System.out.println("Resultat: "+t.evaluate());

Vous devriez obtenir le résultat suivant :

  Resultat: 6.0

Déposez votre nouvelle implémentation de BinaryTree.java ici:

Maintenant, notre programme sait évaluer un arbre qui représente une expression arithmétique. Alors, comment construire l’arbre à partir d’une ligne de commande?

Dans ce but, on va écrire la classe Parse, qui lit une ligne de commande, l’interprète pour construire un arbre sous forme préfixe et affichera l’arbre sous forme infixe. De plus, la classe Parse évalue l’arbre et le dessinera à l’aide de la méthode TreeDraw.drawTree().

Par exemple : (l’étoile est entre guillemets pour éviter que le shell ne la remplace par les noms de fichiers du le répertoire courant.)

 % java Parse + 1 - '*' 10 0.1 32
     ( 1.0 + (( 10.0 *  0.1) -  32.0))
     Resultat: -30.0

Et on doit obtenir le dessin:

Rappelons que les arguments donnés après le nom de la classe par une ligne de commande sont donnés en arguemnt sous forme d’un tableau, à la méthode public static void main(String[] args). Donc, par exemple:

 % java Parse + 1 - '*' 10 0.1 32

nous donne args[0] = “+”, args[1] = “1”, args[2] = “-”, args[3] = “*”, args[4] = “10”, args[5] = “0.1” et args[6] = “32”

REMARQUE: le symbole de multiplication (*) doit être mit entre ' ' pour que le terminal d’Unix n’interprète pas ce symbole mais le passe tel quel à java.

Afin de consommer facilement les symboles de l’entrée un par un, les symboles de la ligne de commande ne seront pas lus directement, mais par l’intermédiaire d’un objet de la classe SymbolReader.java

Ecrire la classe SymbolReader, qui doit implémenter:

• un constructeur SymbolReader (String[] in)
• une méthode String read() qui renvoie (et consomme) un symbole de l’entrée. Si l’entrée est complètement consommée, null est renvoyé.

Par exemple le code suivant copie tout simplement les symboles donnés dans la ligne de commande sur la sortie standard (à tester!).

 class Echo {
   public static void main (String [] args) {
     SymbolReader rd = new SymbolReader(args) ;
     String symb = rd.read();
     while (symb != null) {
       System.out.println(symb) ;
       symb = rd.read() ;
     }
   }
 }

Déposez votre implémentation de SymbolReader.java ici:

La lecture de l’arbre donné sous forme préfixe se fera par une fonction récursive ‘parse’, qui inverse (en quelque sorte) les équations définissant l’ordre préfixe, à savoir

 P(t1, op, t2) = op ; P(t1) ; P(t2)
 P(val) = val

Il est important de supposer que l’entrée représente effectivement un arbre sous forme préfixe.

Dès lors, si le premier symbole de l’entrée est un opérateur (”+”, “-”, “*” ou “/”), alors l’entrée (puisqu’elle est correcte) se poursuit par deux sous-arbres que l’on peut reconnaitre par des appels récursifs.

Sinon, puisque l’entrée est toujours supposée correcte, le premier symbole de l’entrée est la représentation usuelle sous forme de String d’un double (à transformer en double par la méthode static Double.parseDouble(String s))

Compléter la classe Parse:

  class Parse {
     static BinaryTree parse(SymbolReader in) {
      // ...
     }
  
     public static void main(String [] argv) {
       BinaryTree t = parse(new SymbolReader(argv)) ;
       TreeDraw.drawTree(t) ;
    }
  }

Il faut écrire la méthode parse qui renvoie l’arbre contenu sous forme préfixe dans la ligne de commande, de sorte que, par exemple

 % java Parse + '*' 1 2 3

Produit l’affichage

 Resultat: 5

Et dessine l’arbre:

Déposez votre implémentation de Parse.java ici :

Ajouter à la classe BinaryTree une méthode dynamique String infix()

Retournant un texte contenant la notation infixée (complètement parenthésée) de l’expression arithmétique représentée par l’arbre.

En suite, ajouter à la fin du public static void main(String[] args) de la classe Parse une ligne qui permet au programme de prendre en argument une arbre préfixe:

 % java Parse + '*' 1 2 3

Et produit l’affichage :

 Resultat: 5
 (( 1.0 *  2.0) +  3.0)

Et, bien sur, dessine l’arbre:

Déposez votre nouvelle implémentation de BinaryTree.java ici :

Déposez votre nouvelle implémentation de Parse.java ici :