Ce TD sert de préparation au contrôle sur machine de la prochaine scéance. Vous devez donc nécessairement tester les procédures de dépôt et de test de votre programme, ce qui requiert de connaître votre numéro de groupe :
/users/profs/info/INF321/deposer vos_fichiers_java num_groupe
(vous pouvez déposer plusieurs fois, le dernier dépôt fait référence).
Exemple : /users/profs/info/INF321/deposer Noeud.java Calculatrice.java 118
/users/profs/info/INF321/voir num_groupe
Exemple : /users/profs/info/INF321/voir 118
/users/profs/info/INF321/tester numero_test nom_de_classe num_groupe. Des exemples d'utilisation vous sont donnés à la fin de chaque exercice.
Le but de ce TD est de manipuler des arbres en faisant une calculatrice et un peu de calcul formel. Une expression arithmétique peut être codée par un arbre. Par exemple, l'expression (1 + 2 * ((7+8) / (3*4))) + 2 peut être codée par :
Nous avons besoin d'un type pour représenter
soit un nombre entier,
soit une des opérations +, -,
/, *. Pour cela une classe
précompilée Symbole.class
vous est fournie. Il vous suffit de copier ce fichier dans
votre répertoire de travail pour pouvoir utiliser la classe
Symbole. Inutile de connaître le source, il vous
suffit de savoir qu'il ressemble à ceci :
class Symbole
{
Symbole (String l) // Transforme une chaine de caracteres en Symbole
boolean estNombre () // (méthodes non statiques)
boolean estOperation ()
int getNombre ()
char getOperation ()
public String toString ()
}
Voici un exemple d'utilisation :
public static void main (String[] args) {
System.out.println ("Ceci est un exemple d'utilisation de Symbole.") ;
Symbole n = new Symbole ("18") ;
Symbole o = new Symbole ("-") ;
if (n.estNombre() && o.estOperation()) {
if (o.getOperation() == '+') System.out.println ("1 " + o + " " + n + " = " + (1+n.getNombre())) ;
if (o.getOperation() == '-') System.out.println ("1 " + o + " " + n + " = " + (1-n.getNombre())) ;
}
}
}
qui affiche :
viennot@sole$ java Symbole Ceci est un exemple d'utilisation de Symbole. 1 - 18 = -17
Un arbre est fait de noeuds. Un arbre sera donné par un pointeur sur
le noeud racine. Un arbre vide sera représenté par le pointeur
null. Définir une
classe Noeud avec un constructeur
Noeud (Symbole symb, Noeud filsG, Noeud filsD).
Ecrire une fonction static int calcule (Noeud n)
qui calcule la valeur d'une expression.
Test 1.1 Avec la fonction de test suivante :
public static void main (String[] args) {
String unOuAutre = args[0] ;
Noeud zero = new Noeud (new Symbole("0"), null, null) ;
Noeud un = new Noeud (new Symbole (unOuAutre), null, null) ;
Noeud deux = new Noeud (new Symbole ("2"), null, null) ;
Noeud trois = new Noeud (new Symbole ("3"), null, null) ;
Noeud quatre = new Noeud (new Symbole ("4"), null, null) ;
Noeud sept = new Noeud (new Symbole ("7"), null, null) ;
Noeud huit = new Noeud (new Symbole ("8"), null, null) ;
Symbole plus = new Symbole ("+") ;
Symbole moins = new Symbole ("-") ;
Symbole fois = new Symbole ("*") ;
Symbole div = new Symbole ("/") ;
Noeud inter = new Noeud (div, new Noeud (plus, sept, huit), new Noeud (fois, trois, quatre)) ; // (7+8) / (3*4)
Noeud expr = new Noeud (plus, new Noeud (plus, un, new Noeud (fois, deux, inter)), deux) ; // 1 + 2 * ((7+8) / (3*4)) + 2
System.out.println (calcule (expr)) ; // 5
}
on doit obtenir :
viennot@sole$ java Noeud 1 5
Ecrire une fonction afficheSuffixe qui affiche
une expression sous forme suffixe par exemple,
(1 + 2 * ((7+8) / (3*4))) + 2 s'écrit :
1 2 7 8 + 3 4 * / * + 2 +.
Ecrire une fonction afficheInfixe qui affiche
une expression sous forme infixe avec des parenthèses par exemple,
((1 + (2 * ((7 + 8) / (3 * 4)))) + 2).
Test 1.2 Avec la fonction de test suivante :
public static void main (String[] args) {
String unOuAutre = args[0] ;
Noeud zero = new Noeud (new Symbole("0"), null, null) ;
Noeud un = new Noeud (new Symbole (unOuAutre), null, null) ;
Noeud deux = new Noeud (new Symbole ("2"), null, null) ;
Noeud trois = new Noeud (new Symbole ("3"), null, null) ;
Noeud quatre = new Noeud (new Symbole ("4"), null, null) ;
Noeud sept = new Noeud (new Symbole ("7"), null, null) ;
Noeud huit = new Noeud (new Symbole ("8"), null, null) ;
Symbole plus = new Symbole ("+") ;
Symbole moins = new Symbole ("-") ;
Symbole fois = new Symbole ("*") ;
Symbole div = new Symbole ("/") ;
Noeud inter = new Noeud (div, new Noeud (plus, sept, huit), new Noeud (fois, trois, quatre)) ; // (7+8) / (3*4)
Noeud expr = new Noeud (plus, new Noeud (plus, un, new Noeud (fois, deux, inter)), deux) ; // 1 + 2 * ((7+8) / (3*4)) + 2
System.out.println (calcule (expr)) ; // 5
afficheSuffixe (expr) ;
System.out.println () ;
afficheInfixe (expr) ;
System.out.println () ;
}
on doit obtenir :
viennot@sole$ java Noeud 1 5 1 2 7 8 + 3 4 * / * + 2 + ((1 + (2 * ((7 + 8) / (3 * 4)))) + 2)
Vérifiez que le test ci-dessus donne le résultat attendu.
Vous pouvez ensuite déposer et tester (par le test automatique
de correction) votre programme (remplacer
num_groupe par votre numéro de groupe) :
viennot@sole$ /users/profs/info/INF321/deposer Noeud.java num_groupe viennot@sole$ /users/profs/info/INF321/tester 1 Noeud num_groupe
Pour lire en java, il faut utiliser les classes du package
java.io, votre programme doit donc commencer par
import java.io.* ;. Tout programme possède une entrée
"standard" System.in (qui est le pendant de
System.out) qui est de type InputStream.
Pour lire ce qu'il y a dans un fichier, on peut utiliser
InputStream monIn = new FileInputStream
("fichierDEntree.txt") qui renvoie un type particulier
d'InputStream.
Lire avec un InputStream est un peu fastidieux, la
classe BufferedReader permet de lire ligne par ligne
avec la construction :
BufferedReader lecteur = new BufferedReader (new InputStreamReader (monIn)) ;
String ligne = lecteur.readLine () ;
readLine () renvoie null si la fin
du fichier est atteinte.
Ecrire une classe Calculatrice qui lit des symboles
en entrée et les affiche à l'écran. Partir du programme
LireFichier.java qui lit soit
l'entrée standard soit le fichier dont le nom est passé en argument
et affiche simplement ce qui est lu.
Ecrire une fonction
static void lireSymboles (BufferedReader in)
qui lit l'entrée ligne par ligne, construit un symbole à partir de
chaque ligne et affiche le symbole.
Test 2.1 Récupérer test_21.txt. Avec ce fichier en entrée, on doit obtenir :
viennot@sole$ java Calculatrice test_21.txt 1 2 7 8 + 3 4 * / * + 2 +
Vérifiez que le test ci-dessus donne le résultat attendu.
Vous pouvez ensuite déposer et tester (par le test automatique
de correction) votre programme (remplacer
num_groupe par votre numéro de groupe) :
viennot@sole$ /users/profs/info/INF321/deposer Noeud.java Calculatrice.java num_groupe viennot@sole$ /users/profs/info/INF321/tester 2 Calculatrice num_groupe
Chaque fois qu'un nombre est lu, créer un noeud codant l'expression
associée au nombre seul.
Stocker les expressions ainsi créés
dans une liste d'expressions au fur et à mesure
qu'ils sont lus par une fonction
static void lireEtStocke (BufferedReader in).
(Les opérations sont ignorées.)
Pour chaque ligne lue, la liste des expressions est affichée.
On écrira une classe liste de noeuds la plus simple possible
avec une fonction d'affichage statique.
Test 2.2 On doit maintenant obtenir :
viennot@sole$ java Calculatrice test_21.txt 1 2, 1 7, 2, 1 8, 7, 2, 1 8, 7, 2, 1 3, 8, 7, 2, 1 4, 3, 8, 7, 2, 1 4, 3, 8, 7, 2, 1 4, 3, 8, 7, 2, 1 4, 3, 8, 7, 2, 1 4, 3, 8, 7, 2, 1 2, 4, 3, 8, 7, 2, 1 2, 4, 3, 8, 7, 2, 1
Ecrire une fonction
static Liste construitOperation (Symbole op, Liste exprs)
qui retire les deux premieres expressions prem et
deux de la liste, construit l'expression
deux op prem, insère le résultat au début de la liste,
et enfin, renvoie la liste. Les lecteurs avisés remarquerons
que la liste est utilisée comme une pile à la manière des
calculatrices HP.
Ecrire une fonction
static void lireEtConstruit (BufferedReader in)
qui effectue des opérations avec une liste :
quand un nombre est lu, il est inséré dans la liste
et quand une opération est lue, la liste est remplacée par
le résultat de l'opération sur la liste. La liste est toujours
affichée après chaque ligne lue (chaque expression est affichée
sous forme infixe).
Test 2.3 On doit maintenant obtenir :
viennot@sole$ java Calculatrice test_21.txt 1 2, 1 7, 2, 1 8, 7, 2, 1 (7 + 8), 2, 1 3, (7 + 8), 2, 1 4, 3, (7 + 8), 2, 1 (3 * 4), (7 + 8), 2, 1 ((7 + 8) / (3 * 4)), 2, 1 (2 * ((7 + 8) / (3 * 4))), 1 (1 + (2 * ((7 + 8) / (3 * 4)))) 2, (1 + (2 * ((7 + 8) / (3 * 4)))) ((1 + (2 * ((7 + 8) / (3 * 4)))) + 2)
Vérifiez que le test ci-dessus donne le résultat attendu.
Vous pouvez ensuite déposer et tester (par le test automatique
de correction) votre programme (remplacer
num_groupe par votre numéro de groupe) :
viennot@sole$ /users/profs/info/INF321/deposer Noeud.java Calculatrice.java Liste.java num_groupe viennot@sole$ /users/profs/info/INF321/tester 3 Calculatrice num_groupe