¶ Exercice 1 - Manipulation de base
Dans cet exercice, vous avez à disposition 3 piles A, B et C.
- Les éléments sont stockés dans la pile
A. - Les piles
BetCsont des piles temporaires.
Question 1 - Écrire un programme permettant d'inverser l'ordre des éléments de la pile A.
Question 2 - Écrire un programme permettant d'ajouter un élément sur deux dans la pile B et dans la pile C.
Question 3 - Écrire un programme permettant d'ajouter tous les éléments pairs dans la pile B et impairs dans la pile C.
¶ Exercice 2 - La notation polonaise inversée
¶ Présentation
La notation polonaise inversée dite aussi postfixe permet d’écrire sans parenthèses, ni règles de priorité une suite d’opérations arithmétiques qui impliquent des opérateurs et des opérandes.
Pour simplifier, on suppose que l’on n’utilise que les 4 opérateurs + - * / . En écriture postfixe, les deux opérandes d’un opérateur apparaissent avant l’opérateur.
Voici un exemple : l'expression « » s’écrit en postfixe « ».
Question 1 - À la main, convertir l'expression infixe « » en préservant l'ordre des opérations.
Question 2 - À la main, calculer l'expression postfixe « ».
¶ Algorithme de résolution
L'objectif de cet exercice est de construire un programme permettant de calculer le résultat d'une expression postfixe. Ci-dessous le détail de l'algorithme :
- On part d’une pile vide et on lit chaque caractère de l'expression de la gauche vers la droite.
- Si la chaîne lue est un opérande, on l’empile.
- Si c’est un opérateur, on dépile les deux dernières valeurs de la pile, on leur applique l’opérateur et on empile le résultat.
On continue ainsi jusqu’à épuisement de l’expression. À l’issue du programme, la pile ne contient qu’une valeur qui est le résultat de l'expression.
Question 3 - Écrire une fonction calcul. Cette fonction prendre en paramètre 2 entiers et une chaine de caractère représentant un signe + - * /. Cette fonction retourne le résultat du calcul entre les deux nombres selon le signe passé en paramètre.
def calcul(a, b, signe) -> float :
"""
>>> calcul(15, 10, "-")
5.0
>>> calcul(10, 6, "*")
60.0
"""
pass
Question 4 - Écrire une fonction expression_postfixe. Cette fonction prend en paramètre une chaine de caractères représentant une expression postfixe. Elle retourne le résultat de l'expression en suivant l'algorithme détaillé plus haut.
Voici une petite d'animation afin de mieux comprendre l'algorithme
def expression_postfixe(expr) -> float :
"""
>>> calcul("3 5 +")
8
"""
pass
¶ Exercice 3 - Les bonnes parenthèses
On considère une chaîne de caractères comportant des parenthèses ouvrantes et fermantes. L'objectif de cet exercice est d'écrire une fonction qui décèle les anomalies d'écriture.
- L'expression
( () )est correcte, car les parenthèses sont dans le bon ordre. - L'expression
() )n'est pas correcte, la dernière parenthèse n'est jamais ouverte.
Question 1 - Écrire une fonction parenthese_correcte. Cette fonction prend en paramètre une chaine de caractères représentant une expression composée de parenthèses. Elle retourne True si la chaîne est bien formée,False sinon.
def parenthese_correcte(expr) -> bool :
"""
>>> parenthese_correcte('( ) () ( ())')
True
>>> parenthese_correcte('( () ')
False
"""
pass
Notre expression est maintenant composée des caractères [ ], { }, ( ).
Question 4 - Écrire la fonction structure_correcte. Cette fonction améliore la fonction précédente et prend en compte les autres caractères. Elle retourne True si la chaîne est bien formée, False sinon.
¶ Exercice 4 - Conversion infixe vers postfixe
Dans cet exercice, on suppose que l’on dispose d’une expression infixe où chaque opération est parenthésée.
L'objectif de cet exercice est d'écrire une fonction qui permet de transformer une expression infixe ( ( 5 + 3) * 9 ) en expression postfixe 3 5 + 9 *, plus simple à évaluer grâce à l'exercice 2.
¶ Explications
Voici quelques indications pour écrire cette fonction :
-
Il faut vérifier que l’expression infixe est correctement parenthésée.
-
On associe à chaque opérateur un ordre de priorité : les opérateurs
*et/sont de priorité 2, les opérateurs+et-sont de priorité 1 et les parenthèses sont de priorité 0. -
On lit l’expression de la gauche vers la droite :
- Si la chaîne lue est un opérande, on l’empile dans
pile2. - Si la chaîne lue est une parenthèse ouvrante, on l’empile dans
pile1. - Si la chaîne lue est une parenthèse fermante, on dépile
pile1jusqu’à enlever la parenthèse ouvrante correspondante. Chaque opérateur rencontré pendant ce dépilage est empilé danspile2. - Si la chaîne lue est un opérateur, on l’empile dans
pile1après avoir dépilé les éventuels opérateurs déjà présents danspile1verspîle2et qui ont une priorité supérieure ou égale à cet opérateur.
- Si la chaîne lue est un opérande, on l’empile dans
-
Si à l’issue de la lecture, s'il reste des opérateurs dans
pile1, on les dépile et on les empile danspile2.
Voici une petite d'animation afin de mieux comprendre l'algorithme.
Question 1 - Écrire la fonction infixe_to_prefixe. Cette fonction prend en paramètre chaine de caractères représentant une expression infixe. Elle retourne cette même expression sous le format postfixe.
Voici quelques expressions à essayer :
¶ Exercice 4 - Vérificateur de balise HTML
Dans cet exercice, on veut vérifier la bonne structure d'un fichier HTML. Pour simplifier, on n'utilisera que les balises « doubles » (Balises ouvrantes et fermantes).
On considère qu'un document html est bien formé si :
- À chaque balise ouvrante correspond une balise fermante.
- On ne peut fermer une balise que si toutes les balises situées entre les deux balises ouvrantes et fermantes sont fermées.
Par exemple :
- Les documents
ex1.htmletex4.htmlsont bien formés - Les documents
ex2.htmletex3.htmlsont malformés.
On souhaite écrire un programme permettant de déterminer si un fichier html est bien formé.
Pour vous aider à récupérer chaque balise, vous avez à disposition une classe MyHTMLParser. Vous pouvez observer le code de cette classe pour comprendre son fonctionnement.
Voici un exemple permettant de récupérer les différentes balises HTML :
from myhtml_parser import MyHTMLParser
parser = MyHTMLParser("<!DOCTYPE html><html lang=\"fr\"><div>Boonjour</div></html>")
while parser.has_tag():
print(parser.next_tag())
On obtient le résultat suivant :
<html>
<div>
</div>
</html>
Question 1 - Sur le même principe que l'exercice précédent, écrire une fonction verif_html. Cette fonction permet de vérifier la bonne structure d'un fichier html.
¶ Exercice 5 - Le crépier psyco-rigide
À la fin de sa journée, un crêpier dispose d’une pile de crêpes désordonnée. Le crêpier étant un peu psycho-rigide, il décide de ranger sa pile de crêpes, de la plus grande (en bas) à la plus petite (en haut).
Pour cette tâche, le crêpier peut faire une seule action : glisser sa spatule entre deux crêpes et
retourner le haut de la pile. Comment doit-il procéder pour trier toute la pile ?
Dans cet exercice, on modélise une pile de crêpes par une pile d’entiers représentant le diamètre de chaque crêpe. On peut utiliser la fonction suivante qui renvoie une pile de nombres entiers de 1 à n.
def pile_entier_aleatoire(nombre_entier):
from random import shuffle
from Pile import Pile
p = Pile()
nbs = [ x for x in range(1, nombre_entier+1)]
shuffle(nbs)
for nb in nbs:
p.empiler(nb)
return p
Question 1 - Écrire une fonction retourner_pile. Cette fonction prend comme paramètres une pile P et un entier i. Cette fonction inverse l'ordre des i derniers éléments empilés et ne renvoie rien. On pourra utiliser deux piles auxiliaires.
def retourner_pile(pile, i):
pass
Question 2 - Écrire la fonction tri_crepe. Cette fonction prend en paramètre une pile représentant une pile de crêpes. Elle permet de réordonner les crêpes de la plus grande (placée en bas de la pile) à la plus petite (placée en haut de la pile).
- Vous devez utiliser la fonction
retourner_pile.
¶ Exercice 6 - Une file avec 2 piles
Question 1 - Créer une nouvelle classe FileAvec2Pile.
Question 2 - Écrire le constructeur de la classe. Il ne prendra pas de paramètre. Il permettra d'initialiser 2 piles vides AetB comme attribut.
Question 3 - Écrire les différentes méthodes d'une file en utilisant 2 piles pour sauvegarder les éléments de la file.