:: Enseignements :: ESIPE :: E3INFO :: 2023-2024 :: Programmation Objet avec Java ::
[LOGO]

Interface, Polymorphisme, Liaison tardive


Exercice 1 - Arbre d'expressions

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 que + donc il doit apparaître avant dans l'ordre d'évaluation de l'arbre (de gauche à droite).
Comme la notation 4 * 5 + 2 est compliquée à transformer en le bon arbre puisque cela dépend de la priorité des opérateurs, on va utiliser la notation 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 (classes, records, interfaces, ...) devront être définies dans le paquetage fr.uge.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.
    Remarquez que expression définit le première arbre présenté dans le sujet. Dessinez l'arbre à la main correspondant à expression2.
  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 convertir une String en int et il est possible d'utiliser le switch (le switch qui renvoie une valeur) sur des Strings en Java.
    Pour cette question, on ne vous demande pas de vérifier que l'expression fournie en notation préfixe est bien formée. Pour les plus à l'aise, vous pouvez tenter de faire une gestion propre des cas où l'expression est mal-formée.
  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. Déplacer le main dans une nouvelle classe Main dans le package fr.uge.calc.main et faire les changements nécessaires.
  6. 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.
  7. É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 et peut-être des paranthèses inutiles !
  8. 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 ?
  9. 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 ?
  10. Écrire le code de BinOp (dans BinOp.java) et modifier Add, Sub et Mul en conséquence.