Exercices sur les piles et les files

3ème TD, sur les piles et les files.

Pour l’implémentation d’une file avec deux piles, j’utilise une approche objet pour enrober ça joliment, mais le code se comprendra quand même. Il y a deux approches possibles, chacune lente et rapide sur une des opérations push ou pop.

TD3 au Lycée Lakanal (sujet rédigé par Arnaud Basson).

exos_piles_files.creerPileVide()[source]

Créé une pile vide (en O(1)).

exos_piles_files.estVide(p)[source]

Teste si une pile p est vide (en O(1)).

exos_piles_files.push(p, x)[source]

Créé une pile vide (en O(1)).

exos_piles_files.pop(p)[source]

Enlève le sommet de la pile p, et le renvoie (en O(1)).

  • Échoue si la pile est vide (renvoie une erreur).
exos_piles_files.popSecond(p)[source]

Enlève le 2ème élément en partant du somemt de la pile p et le renvoie (en O(1)).

  • Laisse le sommet en place.
  • Échoue si la pile a 0 ou 1 élément (renvoie une erreur).
exos_piles_files.hauteur(p)[source]

Calcule la hauteur n de la pile p (longueur), complexité O(n).

  • Ne modifie pas la pile p.
exos_piles_files.bottomTop(p)[source]

Échange le sommet et le fond de la pile p (p[-1] <-> p[0]) en temps O(n).

class exos_piles_files.file(option=1)[source]

Bases: object

File, implémentée avec deux piles.

Deux options :

  • la première (option=1) est efficace sur pop (O(1)) mais lente sur push (O(n)),
  • la seconde (option=2) est efficace sur push (O(1)) mais lente sur pop (O(n)).

On ne peut pas faire mieux, en fait.

Cf. http://www.geeksforgeeks.org/queue-using-stacks/

__init__(option=1)[source]

Crée une file vide. Option 1 pour être efficace sur pop mais lent sur push, option 2 l’inverse.

push(x)[source]

Enfile x sur le sommet de la file p.

  • O(n) si option=1 (on met p1 sur p2, on push x sur p1, on remet p2 sur p1),
  • O(1) si option=2 (push x sur p1).
pop()[source]

Retire le sommet de la file p et le renvoie.

  • O(1) si option=1 (pop x depuis p1),
  • O(n) si option=2 (on met p1 sur p2, on pop x depuis p2),
estVide()[source]

Teste si la file est vide (en O(1)).

hauteur()[source]

Calcule la hauteur n de la pile p (longueur), complexité O(n).

  • Ne modifie pas la pile p.
__repr__()[source]

Petite fonction pour afficher joliment notre file.

__str__()

Petite fonction pour afficher joliment notre file.

__dict__ = mappingproxy({'__doc__': ' File, implémentée avec deux piles.\n\n Deux options :\n\n - la première (``option=1``) est efficace sur ``pop`` (O(1)) mais lente sur ``push`` (O(n)),\n - la seconde (``option=2``) est efficace sur ``push`` (O(1)) mais lente sur ``pop`` (O(n)).\n\n On ne peut pas faire mieux, en fait.\n\n Cf. http://www.geeksforgeeks.org/queue-using-stacks/', 'pop': <function file.pop>, '__repr__': <function file.__repr__>, 'hauteur': <function file.hauteur>, '__weakref__': <attribute '__weakref__' of 'file' objects>, '__dict__': <attribute '__dict__' of 'file' objects>, 'estVide': <function file.estVide>, '__module__': 'exos_piles_files', 'push': <function file.push>, '__str__': <function file.__repr__>, '__init__': <function file.__init__>})
__module__ = 'exos_piles_files'
__weakref__

list of weak references to the object (if defined)

exos_piles_files.verifier(expr, verb=False)[source]

Vérifie qu’une expression postfixée est valide.

Complexité linéaire dans la taille de l’expression (dans le pire des cas).

On met en oeuvre l’algorithme suivant : On utilise un compteur n valant initialement 0. On lit l’expression à vérifier de gauche à droite :

  • lorsqu’on lit un nombre (entier ou flottant), on incrémente le compteur de 1;
  • lorsqu’on lit un opérateur, on décrémente le compteur de 1.

L’expression est valide si et seulement si le compteur ne prend que des valeurs strictement positives au cours de la lecture de l’expression et s’il vaut 1 à la fin.

On utilise la fonction isinstance pour vérifier si on lit un nombre ou un opérateur.

Note : on vérifie aussi que seuls les opérateurs +, -, *, / et // sont utilisés.

exos_piles_files.evaluer(expr, verb=False)[source]

Évalue l’expression postfixée, en temps linéaire dans sa taille.

  • Le compteur n de la fonction verifier est la longueur de la pile (qui ne doit jamais devenir négative et doit finir égale à 1).
exos_piles_files.evaluer_infixes(expr)[source]

Évaluation d’une expression infixe.

Sortie du script

$ python3 exos_piles_files.py


Exercice 3 : exemples d'expressions :
expr1 : 1 + 2 <-> [1, 2, '+']
expr2 : (1 - 2) + 3 <-> [1, 2, '-', 3, '+']
expr3 : 1 - (2 + 3) <-> [1, 2, 3, '+', '-']
expr4 : 1 - (1+2) * (5 - (3+8)) <-> [1, 1, 2, '+', 5, 3, 8, '+', '-', '*', '-']

Vérifions quelques expressions valides :
[1, 2, '+'] est valide ? True
[1, 2, '-', 3, '+'] est valide ? True
[1, 2, 3, '+', '-'] est valide ? True
[1, 1, 2, '+', 5, 3, 8, '+', '-', '*', '-'] est valide ? True

Plus de détails :
  n = 0 et symbole = 1
  n = 1 et symbole = 1
  n = 2 et symbole = 2
  n = 3 et symbole = +
  n = 2 et symbole = 5
  n = 3 et symbole = 3
  n = 4 et symbole = 8
  n = 5 et symbole = +
  n = 4 et symbole = -
  n = 3 et symbole = *
  n = 2 et symbole = -
[1, 1, 2, '+', 5, 3, 8, '+', '-', '*', '-'] est valide ? True

Vérifions quelques exercises invalides :
1 2 + * 3 <->  [1, 2, '+', '*', 3]
expr5 = [1, 2, '+', '*', 3] est valide ? False
1 2 + 3 4 * <->  [1, 2, '+', 3, 4, '*']
expr6 = [1, 2, '+', 3, 4, '*'] est valide ? False

Plus de détails :
  n = 0 et symbole = 1
  n = 1 et symbole = 2
  n = 2 et symbole = +
  n = 1 et symbole = 3
  n = 2 et symbole = 4
  n = 3 et symbole = *
[1, 2, '+', 3, 4, '*'] est valide ? False

Évaluons quelques expressions valides :
expr1 : 1 + 2 vaut 3 (on attendait 3)
expr2 : (1 - 2) + 3 vaut 2 (on attendait 2)
expr3 : 1 - (2 + 3) vaut -4 (on attendait -4)
expr4 : 1 - (1+2) * (5 - (3+8)) vaut 19 (on attendait 19)

Plus de détails :

  pileValeurs = []
  Symbole lu = 1

  pileValeurs = [1]
  Symbole lu = 1

  pileValeurs = [1, 1]
  Symbole lu = 2

  pileValeurs = [1, 1, 2]
  Symbole lu = +

  pileValeurs = [1, 3]
  Symbole lu = 5

  pileValeurs = [1, 3, 5]
  Symbole lu = 3

  pileValeurs = [1, 3, 5, 3]
  Symbole lu = 8

  pileValeurs = [1, 3, 5, 3, 8]
  Symbole lu = +

  pileValeurs = [1, 3, 5, 11]
  Symbole lu = -

  pileValeurs = [1, 3, -6]
  Symbole lu = *

  pileValeurs = [1, -18]
  Symbole lu = -
expr4 : 1 - (1+2) * (5 - (3+8)) vaut 19 (on attendait 19)

3.3.a) verifier et evaluer sont en O(n) : linéaires dans la longueur de l'expression.

3.3.b) Le compteur n de la fonction ``verifier`` est la longueur de la pile (qui ne doit jamais devenir négative et doit finir égale à 1).

Le fichier Python se trouve ici : exos_piles_files.py.