Listes,Piles,Files

Evaluer une expression arithmétique avec une pile

Pour cet exercice on s’intéresse à l’évaluation d’une expression arithmétique comme 5 + 2 ou (5 + 2) * 3

Evaluer une expression arithmétique comme 5 + 2 c’est lui associer le résultat du calcul ici 7

Pour réaliser cela on va supposer que les expressions sont sous la forme postfixée, c’est à dire que l’opérateur + est écrit après les nombres 5 et 2

Ainsi 5 + 2 est écrit dans une liste sous la forme [5, 2 ,’+’] et (5 + 2) * 3 devient [5,2,’+’,3,’*’]

Regardons sur un exemple

Il s’agit d’évaluer (5 + 2) * 3 en partant de la liste [5,2,’+’,3,’*’] , voici l’algorithme :

  1. On parcourt la liste
  2. Si l’élément lu est un nombre on l’empile sur une pile P
  3. Si l’élément lu est un opérateur parmi ’+’,’-’,’*’ on dépile P deux fois et on calcule le résultat de l’opération associée à l’opérateur et appliquée aux deux éléments dépilés
  4. Ce résultat est empilé sur la pile P
  5. A la fin du parcours de la liste, il reste une seule valeur dans la Pile qui est le résultat du calcul

Calculer le résultat de l’opération associé à l’opérateur se fait par l’intermédiaire d’un dictionnaire qui fait l’association entre le symbole de l’opérateur par exemple ’+’ de type str et la fonction associée appelée somme

Questions

  1. On rappelle les primitives d'une pile

    • creer_pile_vide() qui crée une pile vide
    • est_vide(p) qui renvoie vrai si la pile p est vide et faux sinon
    • empiler(p,x) qui empile la valeur x sur la pile p
    • depiler(p) qui enlève le sommet de la pile p et renvoie cette valeur

    Implémenter ces primitives avec une liste Python

    Créer un dictionnaire operations où les clés sont les caractères '+','-', '*' et '/' et les valeurs associées les noms de fonctions somme,difference, produit et quotient

    Implémenter les fonctions associées

  2. Ecrire une fonction eval(expr) qui prend en paramètre une liste contenant les termes d'une expression postfixée correcte, et qui renvoie la valeur de cette expression avec l'algorithme ci-dessus
  3. Tester sur plusieurs expressions de votre choix

Implémentation d'une file avec un tableau

Définir une classe File_tab, dont les attributs sont

  1. taille un entier égale à la taille du tableau
  2. contenu un tableau de taille égale à taille
  3. tete un entier compris entre 0 et taille - 1, est un indice repérant l'élément en tête de file dans contenu (initialisé à 0)
  4. queue un entier compris entre 0 et taille - 1, est un indice repérant la cellule dans contenu où pourrait venir un nouvel élément dans contenu, à moins que la file soit déjà pleine (initialisé à 0)

les méthodes sont

  1. est_file_vide() qui retourne vrai si la file est vide. C'est le cas lorsque tete == queue

  2. On a fait le choix de ne mettre au plus que taille - 1 éléments dans la file pour pouvoir distinguer les cas où la file est pleine et où la file est vide

    est_file_pleine() qui retourne vrai si la file est pleine . C'est le cas lorsque tete == (queue+1)%taille

  3. enfiler(val) qui ajoute un élément val dans la file si la file n'est pas pleine (ajouter un message d'erreur)
  4. defiler() qui retourne le premier arrivé dans la file si la file n'est pas vide (ajouter un message d'erreur)

Voici un exemple