Exercices sur les piles¶
Classe Pile
Pour réaliser les exercices suivants, vous pouvez réutiliser une classe Pile déjà créée.
Si besoin, vous pouvez télécharger ce fichier pile.py définissant une classe Pile avec les opérations de base sur les piles, à savoir est_vide, empiler et depiler.
Pour utiliser cette classe Pile dans un nouveau programme, placez ce fichier pile.py dans le même répertoire que votre nouveau programme, et ajoutez en tête de votre fichier :
Exercice 1
On souhaite utiliser une pile pour vérifier si une expression arithmétique est bien parenthésée. Écrire une fonction est_bien_parenthesee(chaine) qui renvoie True si l'expression est bien parenthésée, False sinon.
Par exemple :
est_bien_parenthesee('(1 + 3) * (6 + 7)') renverra True.
est_bien_parenthesee('(6 + (4 * 5) - (2 + 1)') renverra False.
Exercice 2
L'écriture polonaise inverse des expressions arithmétiques place l'opérateur après ses opérandes. Cette notation ne nécessite aucune parenthèse ni aucune règle de priorité. Ainsi, l'expression polonaise inverse décrite par la chaîne de caractères 1 2 3 * + 4 * désigne l'expression traditionnellement notée \((1 + 2 \times 3) \times 4\).
La valeur d'une telle expression peut être calculée facilement en utilisant une pile pour stocker les résultats intermédiaires. Pour cela, on observe un à un les éléments de l'expression et on effectue les actions suivantes:
- si on voit un nombre, on le place sur la pile;
- si on voit un opérateur binaire, on récupère les deux nombres au sommet de la pile, on leur applique l'opérateur, et on replace le résultat sur la pile.
Si l'expression était bien écrite, il y a bien toujours deux nombres sur la pile lorsque l'on voit un opérateur, et à la fin du processus il reste exactement un nombre sur la pile, qui est le résultat.
Écrire une fonction prenant en paramètre une chaîne de caractères représentant une expression en notation polonaise inverse composée d'additions et de multiplications de nombres entiers et renvoyant la valeur de cette expression. On supposera que les éléments de l'expression sont séparés par des espaces.
Attention : cette fonction ne doit pas renvoyer de résultat si l'expression est mal écrite.