TD 3: Piles et Files
par Christoph Dürr

 Login :  Mot de passe :

1. Vérificateur de fichier XML

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 : 

  1. Les balises ouvrantes commencent par le nom de la balise suivis éventuellement d'attributs (exemple <a href="http://www.polytechnique.fr">), 
  2. les balises fermantes commencent par un slash suivi du nom de la balise (exemple </a>) 

Voici une définition récursive d'un document XML bien parenthésé : Soit c'est un document sans balises. Soit c'est un document obtenu en concatenant un document sans balises, une balise ouvrante, un document XML bien parenthésé, une balise fermante du même nom, et un document XML bien parenthésé.

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).

Question 1.1 - XmlParser

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>

Question 1.2 - StringList, StringStack

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.

Question 1.3 - VerifyXml

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/*)
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.
(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)

Question 1.4 - VerifyRecursivlyXml (optionnel)


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.


2. Etablissement d'un emploi du temps 

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

Question 2.1 - Schedule

Dans un premier temps on ne va afficher que les débuts des expériences. On vous fournit la classe Experience qui réalise l'agrégat (temps, nom). Ecrivez une classe 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.

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

Question 2.2 - Schedule (suite)

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.

3. Produire l'arbre XML (optionnel)

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];
pour déclarer un sommet qui affichera "A", mais sera appelé "1" dans le reste du document
1->2;
Pour déclarer un arc du sommet 1 vers 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;
}