Interface, Polymorphisme, Liaison tardive

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 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 ambiguë. 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 et 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 Mul).
L'ensemble des classes devront être définies dans le paquetage fr.uge.calc si aucun paquetage n'est indiqué.

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 Add(new Mul(new Value(2), new Value(3)), new Value(4));
        }
       

Et pour Value, Add 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.

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) {
          ...
          System.out.println(expression.eval());
          System.out.println(expression2.eval());
        }
       

Modifier votre code en conséquence.

Écrire une méthode parse qui prend un java.util.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, avec des flèches au niveau des cases) sur des Strings en Java.

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 ?

Déplacer le main dans une nouvelle classe Main dans le package fr.uge.calc.main et faire les changements nécessaires.

Noter que prendre un Scanner en paramètre de la méthode parse n'est pas une bonne pratique, on devrait utiliser une interface plutôt qu'une classe lorsque cela est possible.
Quelle interface que doit-on utiliser à la place de Scanner comme paramètre de la méthode parse ?

É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, uniquement là où cela est nécessaire !

Jusqu'à présent, nous avons utilisé le polymorphisme pour implanter l'évaluation, en ajoutant une méthode eval dans chaque sous-classe de Expr. Il existe une autre façon d'implanter l'évaluation, en utilisant le switch sur les objets, on appelle cette technique le pattern-matching.
On va ajouter une méthode statique evalWithSwitch(expr) dans Expr et mettre en commentaire, les méthodes eval() dans l'interface et les implantations.
Sachant qu'un switch peut avoir des case Type valeur -> ... et qu'un default n'est pas nécessaire si l'on couvre tous les cas possibles, écrire la méthode evalWithSwitch(expr).

On peut simplifier un peu le code précédent car, si par exemple, il existe un record record Pair(String first, String second) {}, dans un switch sur un objet, il est possible au niveau du case de déstructurer un record, comme ceci : case Pair(String first, String second) -> ....
En utilisant ce principe, réécrire le code de la méthode evalWithSwitch(expr).

A votre avis, dans quel cas va-t-on plus utiliser le pattern matching et dans quel cas va-t-on plus utiliser le polymorphisme ?

Entrainement stream

Le fichier StreamsTest.java déclare des méthodes avec en commentaires ce qu'elles doivent produire comme résultat.
Utilisez l'API java.util.stream.Stream pour les implémenter.