Dans ce TD, il s'agit de manipuler des expressions
arithmétiques représentées sous forme d'arbres
de manière similaire à ce qui a été vu en
amphi 5 (voir le transparent 37).
Une expression pourra contenir des entiers,
des opérations
et aussi des variables.
Les variables seront identifiées par un seul caractère,
de 'a' à 'z'. Pour limiter les
problèmes d'arithmétique, on n'utilisera que les 3
opérateurs +, - et *.
Chaque expression constitue donc un arbre, ainsi
6 * ((3-2) + 1) * (9 - 6) * 2
peut-être représenté par l'arbre ci-dessous :
En terminologie d'arbre, les entiers et les variables sont des feuilles (ils n'ont pas de fils) et les opérations sont des noeuds internes.
On va définir une classe Expr dont chaque objet
correspond à un noeud d'une expression. On propose
dans ce TD deux options de codage pour différencier les trois
natures d'expression.
La première plus simple consiste à ne définir qu'une seule classe
avec un champ nature indiquant la nature
(entier, opération ou variable). Si vous vous sentez à
l'aise avec les interfaces et les méthodes non statiques,
vous pouvez choisir la deuxième
option consistant à définir Expr comme une interface
avec trois classes différentes la réalisant.
Un objet de la classe
Expr contiendra un champ
nature indiquant la nature de l'expression
(entier, opération ou variable).
Pour plus de lisibilité, on utilisera trois constantes
INT, OP et VAR
pour identifier ces trois natures.
On pourra ainsi effectuer un traitement en fonction
de la nature d'une expression e par la syntaxe :
switch (e.nature) {
case Expr.INT: ... break ;
case Expr.OP: ... break ;
case Expr.VAR: ... break ;
default: throw new Error ("Nature inconnue : " + e.nature) ;
}
Rappelons que dans une utilisation rationnelle du switch,
toute suite de une ou plusieurs
instructions d'un case doit
se terminer soit par un break (qui sort du
switch), soit par un return ...
(qui sort de l'appel de fonction en cours).
Un objet de la classe
Expr contiendra de plus un champ
entier (utilisé dans le cas d'un entier),
un champ caractère (utilisé dans le cas d'une variable),
un autre champ
caractère (utilisé dans le cas d'une opération)
et deux champs
expressions, ses fils gauche et droit.
La classe Expr aura 3 constructeurs :
Expr(int i) qui permet de construire un noeud « entier »,
Expr(char c) qui permet de construire un noeud « variable »,
Expr(char op, Expr left, Expr right) qui permet de
construire un noeud « opération »,
l'opération étant codé par
l'un des 3 caractères '+', '-' et '*'.
Écrire la définition de la classe Expr avec les
trois constructeurs requis.
Voici deux exemples d'utilisation :
class Calcul
{
public static void main (String[] args) {
Expr e1 = new Expr( '*', new Expr('x'), new Expr(10));
Expr e2 = new Expr( '*',
new Expr( '*',
new Expr( '*',
new Expr(6),
new Expr( '+',
new Expr( '-',
new Expr(3),
new Expr(2)),
new Expr(1))),
new Expr( '-',
new Expr(9),
new Expr(6))),
new Expr(2));
}
}
Définir une interface Expr
avec la syntaxe interface Expr { ... }
(les méthodes à définir
dans cette interface seront explicitées au fur et à mesure
des questions suivantes).
Définir trois classes ExprInt,
ExprVar, et ExprOp implémentant
cette interface
(avec la syntaxe class ExprInt implements Expr { ... }).
Chacune de ces classes aura un constructeur
permettant de construire respectivement un entier, une
variable ou une opération.
On pourra ainsi construire les deux exemples ci-dessous :
class Calcul
{
public static void main (String[] args) {
Expr e1 = new ExprOp( '*', new ExprVar('x'), new ExprInt(10));
Expr e2 = new ExprOp( '*',
new ExprOp( '*',
new ExprOp( '*',
new ExprInt(6),
new ExprOp( '+',
new ExprOp( '-',
new ExprInt(3),
new ExprInt(2)),
new ExprInt(1))),
new ExprOp( '-',
new ExprInt(9),
new ExprInt(6))),
new ExprInt(2));
}
}
Dans cette partie, les signatures des méthodes (c'est à dire
le type des variables prises en arguments ainsi que le type
de ce qui est retourné) sont volontairement omises. Le premier
travail pour chaque question consiste donc à deviner une
signature correcte. Dans le cas de l'option 1.1, il est
impératif d'utiliser un style similaire à l'utilisation
du switch décrite plus haut.
On pourra au choix utiliser des méthodes statiques ou des méthodes non statiques (plus naturelles notamment pour l'option 1.2). Les indications en vert (comme ceci) ne concernent que ceux ayant choisi l'option 1.2 (avec interface).
printPrefix permettant d'afficher une
expression sous forme préfixe.printPrefix dans l'interface Expr
avec une définition adaptée dans chacune des classes
ExprInt, ExprVar
et ExprOp. Remarquons que toutes
les méthodes déclarées dans une interface doivent ensuite
être déclarées public dans les classes qui
l'implémentent.
printPrefix (e1) ; System.out.println() ;
printPrefix (e2) ; System.out.println() ;
* x 10
* * * 6 + - 3 2 1 - 9 6 2
printInfix qui affichera une écriture
complètement parenthésée,
donnant par exemple :
(x * 10)
(((6 * ((3 - 2) + 1)) * (9 - 6)) * 2)
value
qui retourne la valeur d'une expression
en supposant qu'elle ne contient
pas de variables.
System.out.println (value(e2)) ; donne 72.
derive
qui prend en argument une expression et un caractère représentant
un nom de variable, et
qui retourne la dérivée partielle
de l'expression selon la variable.
On appliquera les formules générales de dérivation
comme, (f.g)' = (f)'.g + f.(g)', sans chercher à simplifier.
printInfix (derive (e1, 'x')) ; donnera
((1 * 10) + (x * 0)).
La simplification d'une telle expression pourra être traitée en supplément.
readPrefix
qui lit une expression sous
forme préfixe depuis le clavier et renvoie l'expression lue.
On utilisera pour cela la méthode suivante qui permet de
lire un caractère tapé au clavier :
static char getChar () {
try { // On essaye de lire un caract`ere par System.in.read() :
return (char) System.in.read () ;
} catch (java.io.IOException e) { // En cas de probl`eme :
throw new Error ("Probl`eme d'entr'ee sortie.") ;
}
}
L'algorithme est le suivant : on lit un caractère
par getChar ;
si c'est un blanc, on passe au suivant ;
si c'est un chiffre on considère que l'expression
est un entier à un seul chiffre (voir les indications
ci-dessous) ; si c'est une lettre, on considère qu'il s'agit
d'une variable de nom la lettre en question enfin,
s'il s'agit de +, - ou
*, il s'agit d'une opération dont les fils gauche
puis droit sont lus par des appels récursifs.
Si on rencontre un autre caractère, on produira une erreur.
0 et 9. Pour savoir si le caractère
c est un chiffre, on peut utiliser le prédicat
Character.isDigit (c). La conversion en l'entier
correspondant se fait alors par
Character.getNumericValue (c).
c est un espace, on peut
utiliser le prédicat Character.isWhitespace(c).
c est une lettre, on peut utiliser le prédicat
Character.isLetter (c).
getChar ci-dessus bloque
jusqu'à ce qu'une ligne entière ait été tapée. Plusieurs appels
à getChar
renvoient alors les caractères un à un. (Pour plus d'informations,
getChar se contente d'appeler la méthode non
statique read() de la variable
System.in qui est de type
java.io.InputStream. La syntaxe try { ... } catch ... sert à
gérer le cas où une exception se produit. Une exception
est un peu comme une erreur produite par
throw new Error()
sauf qu'on peut la « rattraper » par
cette syntaxe et gérer le cas où elle se produit.)
Une solution par l'option 1.1.
Définir la méthode public String toString ()
de votre (ou vos) classe(s) qui renverra une chaîne codant
l'expression sous forme préfixe.
Rappelons que l'on peut convertir un entier i
en chaîne de caractères par "" + i
(de même pour un caractère c avec "" + c).
Pour une implémentation plus efficace, utiliser maintenant
la classe StringBuffer.
(Voir aussi les transparents 5 à 8 de l'amphi 6.)
Écrire une méthode addToString
qui ajoute une description de l'expression à un StringBuffer passé en argument.
Ainsi, on pourra renommer la méthode toString
précédente en toString2 et utiliser :
public String toString () {
StringBuffer sb = new StringBuffer () ;
addToString (sb) ;
return sb.toString () ;
}
(Dans le cas de l'option 1.2
(avec interface), on remarquera qu'il n'est pas utile de modifier
les méthodes toString de toutes les classes.)
Ceux qui ont utilisé l'option 1.1 jusqu'ici
peuvent passer à l'option 1.2 ici. On pourra
alors traiter en priorité dans la partie 2
les questions 2.1 (dans le cadre de toString
comme ci-dessus), et 2.6.
Comparer la rapidité des deux méthodes toString
sur le fichier
bigexpr.txt contenant une expression
sous forme préfixe.
On utilisera comme au TD 3
des appels à TC.demarrerChrono()
et System.err.println (TC.tempsChrono()
+ " millisecondes").
Si votre programme Calcul
lit une expression au clavier, vous pouvez lire l'expression
contenue dans bigexpr.txt
par la commande :
java Calcul < bigexpr.txt
Une solution par l'option 1.2.
Déposez vos fichiers en utilisant la ligne de commande :
/users/profs/info/Depot/INF_421/deposer vos_fichiers_java TD_6 votre_groupe
où vos_fichiers_java est la liste des fichiers que vous déposez (séparés par des espaces) et votre_groupe est votre numéro de groupe en informatique (entre 1 et 6).
Quelques exercices de plus.
Last modified: Thu Sep 30 09:51:38 CEST 2004