Énumérations, design Pattern de Visiteur

Exercice 1 - Évaluation d'expressions arithmétique préfixes

On souhaite pouvoir évaluer des expressions arithmétiques sur des double utilisant dans un premier temps uniquement des additions et des soustractions. De plus, on veut saisir ces expressions sur l'entrée standard (Scanner).

1. Dans un premier temps, on utilisera PLUS et MINUS au lieu des opérateurs « +»  et « -» . Par exemple:

   > java EvalPrefixe
   MINUS PLUS 5 7 PLUS 1 2
   9,000000
   

   Pour cela, déclarer le type énuméré Operation correspondant regroupant PLUS et MINUS, et écrire une méthode récursive static double eval(Scanner sc) qui réalise l'évaluation.
2. Pour permettre de traiter les entrées de type

   > java EvalPrefixe
   - + 5 7 + 1 2
   9,000000
   

   il faut associer à chaque opérateur (« +» , « -» ) une opération du type énuméré (PLUS, MINUS). Faites cela en utilisant une table de hachage statique.
3. Pour éviter de devoir remplir « à la main»  la table de hachage, il est possible de munir chaque valeur de l'énumération d'une méthode operatorSign() qui donne la chaîne de caractères représentant cette opération (qui à PLUS associe « +» ). La table de hachage peut alors être remplie de manière générique comme ceci :

   for (Operation op : Operation.values())
     map.put(op.operatorSign(), op);
   

4. Comment faire en sorte que l'ajout d'une nouvelle opération ne modifie que le type énuméré (et non la méthode eval()).

Exercice 2 - Arbre syntaxique des opérations arithmétiques

Toujours dans le domaine des expressions arithmétiques, on désire maintenant construire l'AST (Abstract Syntax Tree) des expressions. Pour cela, créer des types Expr (expressions génériques), BinOp (opérateurs binaires génériques), Const, Plus et Minus (classes concrètes).

1. Écrire, sur le modèle de l'exercice précédent, un parseur qui construit l'arbre syntaxique de l'expression arithmétique tapée sur l'entrée standard.
2. Le design-pattern de Visiteur permet de spécifier des algorithmes à l'extérieur des structures de données sur lesquelles ils s'appliquent. Pour cela, les structures de données sont munies d'une méthode accept(). Par exemple, vous devrez ajouter dans toutes les classes concrètes de l'AST le code suivant :

   public void accept(ExprVisitor v) { v.visit(this); }
   

   Par ailleurs, les algorithmes doivent implanter l'interface ExprVisitor suivante :

   interface ExprVisitor {
     public void visit(Const c);
     public void visit(Plus p);
     public void visit(Minus m);
   }
   

3. Est-il possible de ne mettre la méthode accept() que dans la super-classe commune à tous les types de noeuds (Expr) (la méthode aurait alors été héritée dans tous les sous-types) ? Pourquoi ?
   
4. Écrire une classe ToStringExprVisitor qui implante l'interface ExprVisitor pour réaliser l'affichage infixe de l'AST que votre parseur a construit (modifications de Expr et ses sous-types interdites).
5. Écrire une classe de visiteur qui évalue l'AST que votre parseur a construit (modifications de Expr et ses sous-types interdites).
6. Modifier les codes précédents pour avoir des visiteurs dont les méthodes visit() retournent quelque chose.