Exercices

Exercice 1

Pour chacune des situations suivantes, donnez la structure de données la plus adaptée.

1. La gestion du flux de personnes arrivant dans une préfecture.
2. Les opérations effectuées dans un logiciel de dessin pour que l'on puisse les annuler.
3. Envoyer des fichiers à un serveur d'impression.
4. Un répertoire téléphonique ou l'on accède au téléphone en rentrant un nom.
5. Mémoriser tous les coups d'une partie d'échecs.

Exercice 2

Énoncé

Nous allons créer une fonction check permettant de vérifier le bon parenthésage d'une expression. Nous considérons les symboles (, ), [, ], { et }. Voici quelques exemples de bon parenthésage :

(abcd) {edftr [rtyh]}
er[rtko (ertg ( rttre) ertt {erttert})]

Voici maintenant des exemples de mauvais parenthésage :

(zer{ert)}
er{erzerpo[rer]rtert
zeze(rerf)rertr}

Pour faire cela, nous allons utiliser une pile. En parcourant la chaine de caractère à tester, il faut empiler les caractères ouvrant et dépiler lorsqu'on rencontre le même caractère fermant.

Si lorsqu'on dépile ce n'est pas le même caractère, il y a un problème.
Si lorsqu'on dépile la pile est vide, il y a un problème.
Si à la fin du parcourt de la chaîne, la pile n'est pas vide il y a un problème.

Développer les fonctionalités croissantes suivantes :

Détecter et annoncer les trois problèmes décrits ci-dessus (voir les tests).
Indiquer par une flèche la position du caractère qui pose problème (voir les tests)
Indiquer par une deuxième flèche lorsqu'il y a lieu le caractère correspondant au caractère à problème (voir les tests)

Tests

Pour la question 1 :

# Caractère fermant en trop
>>> check("P{h(ra)se} [d{e te}]st}")
Caractère fermant en trop

# Manque un caractère fermant
>>> check("P{h(ra)se [d{e te}]st")
Manque un caractère fermant

# Mauvais caractère fermant
>>> check("P{h(ra)se} [d{e te})st")
Mauvais caractère fermant

Pour la question 2 :

# Caractère fermant en trop
>>> check("P{h(ra)se} [d{e te}]st}")
P{h(ra)se} [d{e te}]st}
                      ^

# Manque un caractère fermant
>>> check("P{h(ra)se [d{e te}]st")
P{h(ra)se [d{e te}]st
                     ^

# Mauvais caractère fermant
>>> check("P{h(ra)se} [d{e te})st")
P{h(ra)se} [d{e te})st
                   ^

Pour la question 3 :

# Caractère fermant en trop
>>> check("P{h(ra)se} [d{e te}]st}")
P{h(ra)se} [d{e te}]st}
                      ^

# Manque un caractère fermant
>>> check("P{h(ra)se [d{e te}]st")
P{h(ra)se [d{e te}]st
 ^                   ^

# Mauvais caractère fermant
>>> check("P{h(ra)se} [d{e te})st")
P{h(ra)se} [d{e te})st
           ^       ^