Interface, Polymorphisme, Liaison tardive

Le but de cet exercice est de construire un parseur d'expressions arithmétiques simples. Ces expressions sont représentées sous forme d'arbres, par exemple 2 + 3 est représenté par

         +
       /   \
      2     3
    

et 4 * 5 + 2

         +
       /   \
      *      2
    /   \
   4     5
    

car * est plus prioritaire de + donc il doit apparaitre avant dans l'ordre d'évaluation de l'arbre (de gauche à droite).
Comme la notation 4 * 5 + 2 est compliquée à transformer dans le bon arbre puisque cela dépend de la priorité des opérateurs, on va utiliser la notaion préfixe, celle où on met l'opérateur devant car celle-ci n'est pas ambigue. En notation préfixe, cela donne + * 4 5 2
Pour représenter la valeur on utilisera le type Value, pour représenter l'opérateur '+', on utilisera le type Add, pour représenter l'opérateur '-', on utilisera le type Sub et enfin pour représenter l'opérateur '*', on utilisera le type Mul.
On peut remarquer que pour un opérateur, le fils gauche ou le fils droit peuvent être soit un autre opérateur soit une valeur, il va donc nous falloir un type que l'on va appeler Expr qui représente toutes les valeurs possibles (un Value ou un Add ou un Sub ou un Mul).
L'ensemble des classes devront être définies dans le paquetage fr.umlv.calc si aucun paquetage n'est indiqué.

1. On va créer Expr dans un fichier Expr.java avec le main suivant

           public static void main(String[] args) {
             Expr expression = new Add(new Value(2), new Value(3));
             Expr expression2 = new Sub(new Mul(new Value(2), new Value(3)), new Value(4));
           }
          

   
   Et pour Value, Add, Sub et Mul, on utilisera des records chacun dans son propre fichier .java.
   Créer les records avec leurs composants nécessaires pour que le main compile.
2. On souhaite maintenant pouvoir évaluer (trouver la valeur) d'une expression (Expr) en appelant la méthode eval comme ceci

           public static void main(String[] args) {
             Expr expression = new Add(new Value(2), new Value(3));
             Expr expression2 = new Sub(new Add(new Value(2), new Value(3)), new Value(4));
             System.out.println(expression2.eval());
           }
          

   Modifier votre code en conséquence.
3. Écrire une méthode parse qui prend un Scanner en entrée et crée l'arbre d'expression correspondant sachant que l'arbre sera donné au scanner en utilisant la notation préfixe (opérateur devant). Par exemple, au lieu de 2 + 3 - 4, la notation préfixe est - + 2 3 4.
   Indication : la méthode parse est naturellement récursive. Si l’expression contient encore des symboles (et qu'elle est bien formée) alors:
   • soit le prochain symbole est un opérateur et il faut appeler parse() 2 fois pour obtenir le fils gauche et le fils droit et les combiner avec l'opérateur pour faire une nouvelle expression.
   • soit le prochain symbole est un entier et il suffit d'en faire une feuille de l’arbre d'expression,
   
   Enfin, pour rappel, scanner.next() renvoie le prochain mot, Integer.parseInt() permet de savoir si c'est un entier et il est possible d'utiliser le switch expression (le switch qui renvoie une valeur) sur des Strings en Java.
4. Il y a un bug dans le code que l'on a écrit, on permet à n'importe qui d'implanter Expr mais cela ne marchera pas avec la méthode parse qui elle liste tous les sous-types possibles.
   Comment corriger ce problème ?
5. En fait, les records n'ont pas besoin d'être déclarés dans leur propre fichier .java, il peuvent être tous déclarés dans le fichier Expr.java en tant que membre (attribut) de la classe Expr.
   Faire le changement et expliquer pourquoi c'est intéressant.
6. Déplacer le main dans une nouvelle classe Main dans le package fr.umlv.calc.main et faire les changements nécessaires.
7. Noter que prendre un Scanner en paramètre ne permet pas de ré-utiliser la méthode parse si, par exemple, l'expression à parser est stockée dans une List de String.
   Quelle interface que doit-on utiliser à la place de Scanner pour que l'on puisse appeler la méthode parse avec un Scanner ou à partir d'une List.
8. Écrire la méthode d'affichage de l'arbre d'expression pour que l'affichage se fasse dans l'ordre de lecture habituel.
   Note : il va falloir ajouter des parenthèses !
9. Enfin, on peut voir que le code de eval dans Add, Sub et Mul est quasiment identique, dans les trois cas : la méthode eval est appelée sur left et right.
   On souhaite factoriser ce code (on ne le ferait probablement pas dans la vraie vie car il n'y a pas assez de code à partager, mais ce n'est pas la vraie vie, c'est un exercice) en introduisant un type intermédiaire BinOp, sous-type de Expr et super-type de Add, Sub et Mul.
   Le type BinOp doit-il être un record, une classe ou une interface ?
10. Sachant que l'on veut écrire eval dans BinOp, comment eval doit être déclarée ? Et comment, dans eval de BinOp, peut-on accéder aux champs left et right, qui sont déclarés dans Add, Sub et Mul ?
11. Écrire le code de BinOp (dans Expr.java) et modifier Add, Sub et Mul en conséquence.