Le but de cet exercice est d'apprendre à manipuler les piles. Pour cela on va écrire un programme qui vérifie si un fichier XML est bien parenthésé. --- Encore ? Oui c'est un rappel sur le cours inf311. --- Pour ce TD nous adoptons une définition simplifiée par rapport à la définition officielle. Un fichier XML est un fichier texte qui contient des balises (tag en anglais). Les balises sont délimitées par des chevrons ('<' et '>') et sont de deux types :
<a
href="http://www.polytechnique.fr">), Voici une définition récursive d'un
Par exemple les documents
<a><b></b></a><b></b>
ou
1<b><a></a><a>2</a></b>
sont bien paranthèsés alors que les documents
<a></b> ou </c> ne le
sont pas.
| Règle de Douglas Hofstädter: les choses durent toujours plus longtemps que prévu, même en tenant compte de la règle de Douglas Hofstädter. |
| Fig 1: une autre définition récursive |
Pour vous épargner les difficultés des
entrées/sorties sur des fichiers, nous vous fournissons une
classe XmlParser. Son constructeur prend en
paramètre un nom de fichier. Elle ouvre alors le fichier et le
découpe alternativement en balises et en texte entre les
balises. Vous pouvez alors appeler successivement sa méthode
nextString() qui retournera une par une les chaînes
résultant de la découpe, puis finira par retourner null
quand la fin du fichier est atteinte. Cette classe contient aussi des
tests boolean isTag(String s), boolean
isOpeningTag(String s), boolean
isClosingTag(String s) qui font exactement ce que vous pensez
qu'elles font et une méthode pour extraire le nom d'une
balise String tagName(String tag).
On va commencer par se familiariser avec la classe
XmlParser. A cet effet, la
méthode main de la classe donne un exemple
d'utilisation de ses méthodes.
public static void main(String args[]) {
if (args.length!=1)
throw new Error("usage: java XmlParser <filename>");
// XmlParser d'ecoupe le fichier en balises et texte entre les balises
XmlParser parser = new XmlParser(args[0]);
String s;
int indent=0; // niveau d'imbriquation
// nextString retourne la prochaine cha^ine,
// et retourne null quand la fin du fichier est atteinte
while ((s = parser.nextString()) != null)
if (XmlParser.isTag(s)) { // aha! une balise
if (XmlParser.isClosingTag(s))
indent--;
// indenter
for (int i=0; i<indent; i++)
System.out.print(" ");
System.out.println(s);
if (XmlParser.isOpeningTag(s))
indent++;
}
}
Exécutez le programme XmlParser avec le
fichier petit.xml. Vous devriez voir le résultat
suivant.
<carnet>
<note>
<titre>
</titre>
<ligne>
</ligne>
<ligne>
</ligne>
</note>
<note>
<titre>
</titre>
<ligne>
</ligne>
</note>
</carnet>
Vous vous doutez sûrement qu'il conviendrait d'utiliser une pile pour vérifier qu'un document XML est bien paranthèsé. Nous pourrions utiliser la classe Stack, mais pour cet exercice il est préférable que vous écriviez vous même une liste de chaînes.
Commencez par écrire une classe StringList. Le
constructeur prend en paramètre une chaîne de
caractères s et une StringList l,
créant ainsi une liste qui commence par s et
continue par la sous-liste l.
Puis écrivez une classe StringStack avec les
méthodes void push(String s), String
pop() et boolean isEmpty(). Inspirez vous du poly.
En fait vous pouvez
mettre les deux classes dans un même fichier StringStack.java
pourvu que StringList ne soit pas public.
Testez avec le code
suivant qui devrait s'exécuter sans erreur.
public static void main(String args[]) {
StringStack stack = new StringStack();
assert stack.isEmpty();
stack.push("a"); stack.push("b");
assert !stack.isEmpty();
assert stack.pop().equals("b");
assert stack.pop().equals("a");
assert stack.isEmpty();
System.out.println("Test r'eussi.");
}
Soit dit en passant, assert est une
instruction Java bien utile qui permet de tester une condition et
d'arrêter brutalement le programme si elle n'est pas satisfaite
avec un message contenant la condition violée et la ligne du
code source concernée.
Finalement en partant du main de la classe XmlParser
écrivez la
classe VerifyXml qui vérifie à l'aide de la
pile
créée précédemment si un fichier
donné est
un document XML bien paranthèsé. Prenez un moment
pour réfléchir à l'algorithme utilisé.
Testez votre programme à l'aide des fichiers XML donnés. Voilà le genre de résultats que vous devriez obtenir.
$ foreach f (fichiers_xml/*)(Si vous faites cet exercice sous MacOSX ou GNU/Linux au lieu de foreach écrivez for f in fichiers_xml/*; do java VerifyXml $f; done)
java VerifyXml $f
end
fichiers_xml/erreur1.xml: Erreur : balise <a> n'est pas ferm'ee.
fichiers_xml/erreur2.xml: Erreur : balise </a> sans balise ouvrante correspondante.
fichiers_xml/erreur3.xml: Erreur : balise </b> lu, mais </a> attendu.
fichiers_xml/erreur4.xml: Erreur : balise </b> lu, mais </c> attendu.
fichiers_xml/erreur5.xml: Erreur : balise </c> lu, mais </b> attendu.
fichiers_xml/experiences.xml: Ce document XML est bien parenth'es'e.
fichiers_xml/graphe.gxl: Ce document XML est bien parenth'es'e.
fichiers_xml/petit.xml: Ce document XML est bien parenth'es'e.
| Pourquoi est-ce que les
informaticiens meurent-ils
sous la douche ? Parce que sur les flacons de shampooing il y a écrit "Appliquer sur les cheveux mouillés, rincer, puis recommencer.". |
| Fig 2: pensez à la terminaison des appels récursifs |
Maintenant refaisons l'exercice précédent sans
l'utilisation de
StringStack en utilisant la pile des appels de Java.
La classe VerifyRecursivlyXml dotée d'une
méthode
récursive boolean verify(XmlParser doc)
implémente un
test récursif qui est calqué sur la définition des
documents XML bien parenthésés. Par contre une erreur
s'est introduite
dans ce code.
Vous pouvez vous en rendre
compte en l'exécutant sur le jeu de tests fourni et en comparant
le
code avec la définition des
documents XML bien parenthésés. Trouvez et
corrigez l'erreur. Une seule ligne est à changer.
Le but de cet exercice est d'apprendre la manipulation des files.
Khalid travaille dans un laboratoire de biologie et doit intervenir en début et en fin des expériences qui sont programmées tout au long d'une journée. Pour cela il reçoit un fichier XML qui décrit la liste des expériences à réaliser dans une journée, avec leur heure de début et leur nom. Le fichier est formaté comme dans l'exemple ci-dessous, les entrées sont triées par heure de début, qui est représentée par le nombre de minutes depuis minuit (exemple 615 représente 10h15).
<experience>
<debut>615</debut>
<nom>crystalline D-Tyr-tRNA(Tyr) deacylase</nom>
</experience>
<experience>
<debut>680</debut>
<nom>methionyl-tRNA transformylase</nom>
</experience>
<experience>
<debut>720</debut>
<nom>matrix-assisted laser desorption/ionization mass spectrometry</nom>
</experience>
Chaque expérience dure exactement 90 minutes. Nous voulons fournir à Khalid une liste ordonnée des débuts et fins d'expériences dans le format suivant.
d'ebut 10h15 crystalline D-Tyr-tRNA(Tyr) deacylase
d'ebut 11h20 methionyl-tRNA transformylase
fin 11h45 crystalline D-Tyr-tRNA(Tyr) deacylase
d'ebut 12h00 matrix-assisted laser desorption/ionization mass spectrometry
fin 12h50 methionyl-tRNA transformylase
fin 13h30 matrix-assisted laser desorption/ionization mass spectrometry
Schedule qui lit un fichier XML indiquée
ci-dessus et l'affiche de la façon suivante. Déclarez une
variable Experience
exp. Répétez les instructions suivantes
jusqu'à ce que la fin du fichier soit atteinte.
nextString
du parcoureur XML (ParseXml) est <debut>,
mettez dans exp.time
le nombre codé par la prochaine chaîne, que vous pouvez
extraire avec parseInt.
nextString
est <nom>, mettez dans exp.name
la prochaine chaîne. nextString
est </experience>,
affichez exp.
Veillez à ne pas appeler nextString lors de chacun
des trois tests, sinon vous comparerez des chaînes
différentes.
Sur le fichier experiences.xml votre code devrait
produire la sortie suivante :
10h15 crystalline D-Tyr-tRNA(Tyr) deacylase
11h20 methionyl-tRNA transformylase
12h00 matrix-assisted laser desorption/ionization mass spectrometry
Pour entrelacer la liste des débuts et la liste des
fins d'expériences nous allons utiliser une file, en utilisant
la classe LinkedList fournie par la bibliothèque Java.
Pensez à importer java.util.*. On
stockera dans la file les expériences en cours. Prenez un
moment pour lire la documentation de la classe LinkedList
pour trouver les méthodes qui permettent d'ajouter, d'enlever et
d'accéder à la tête de file.
Ecrivez la classe Schedule qui ouvre un fichier XML
donné en paramètre puis affiche la liste des
débuts et fins d'expériences ordonnés par heure.
Souvenez-vous, une expérience dure exactement 90 minutes.
Pour
cela créez une file des expériences en cours. Pour chaque
expérience E effectuez les actions suivantes.
Commencez par ajouter E à la file.
Puis tant
que la tête de file est une expérience qui terminera avant
le début de E, on l'enlève de la file et on
l'affiche. Alors
seulement
on affiche le début de E.
L'exercice optionnel consiste à produire un arbre qui
représente la structure d'un document XML. Pour cela on va
produire un graphe dans le format standard DOT. Dans ce
format la première ligne contient digraph {
(pour graphe dirigé) et la dernière ligne contient
}. Les autres lignes sont de deux types.
1 [label=A]; 1->2;
Il y a de nombreux visualiseurs de graphe qui savent lire ce format,
dont dot sur Unix. Pour visualiser le graphe produit par votre
programme utilisez la commande Unix
suivante :
java XmlTree fichiers_xml/petit.xml | dot -Tpng | xv -Si jamais dot n'est pas installé sur votre machine vous pouvez couper/coller la sortie dans cette page.
Le graphe ainsi produit sur l'exemple petit.xml aura cette forme
digraph {
0 [label="carnet"];
1 [label="note"];
0->1;
2 [label="titre"];
1->2;
3 [label="ligne"];
1->3;
4 [label="ligne"];
1->4;
5 [label="note"];
0->5;
6 [label="titre"];
5->6;
7 [label="ligne"];
5->7;
}