#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ TD3 au Lycée Lakanal (sujet rédigé par Arnaud Basson). - *Date :* jeudi 22 octobre 2015, - *Auteur :* Lilian Besson, pour le cours d'informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/), - *Licence :* MIT Licence (http://lbesson.mit-license.org). """ from __future__ import print_function # Python 2 compatibility # %% Exercice 1 : Manipulation de piles # Implémentation abstraite de piles def creerPileVide(): """ Créé une pile vide (en O(1)).""" return [] def estVide(p): """ Teste si une pile p est vide (en O(1)).""" return len(p) == 0 def push(p, x): """ Créé une pile vide (en O(1)).""" p.append(x) def pop(p): """ Enlève le sommet de la pile p, et le renvoie (en O(1)). - Échoue si la pile est vide (renvoie une erreur). """ x = p.pop() return x # a) def popSecond(p): """ 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). """ x = pop(p) y = pop(p) push(p, x) return y # b) Hauteur, ne peut pas utiliser len() de Python, mais doit pop puis push toutes les valeurs def hauteur(p): """ Calcule la hauteur n de la pile p (longueur), complexité O(n). - Ne modifie pas la pile p. """ n = 0 # On déplace les valeurs dans p vers p2 une autre pile p2 = creerPileVide() while not estVide(p): x = pop(p) push(p2, x) n += 1 # n = len(p) maintenant, on doit déplacer dans l'autre sens while not estVide(p2): x = pop(p2) push(p, x) return n # c) def bottomTop(p): """ Échange le sommet et le fond de la pile p (p[-1] <-> p[0]) en temps O(n).""" # On dépile top = pop(p) p2 = creerPileVide() while not estVide(p): x = pop(p) push(p2, x) bottom = pop(p2) # On rempile push(p, top) while not estVide(p2): x = pop(p2) push(p, x) # Ordre inchangé pour ces valeurs là push(p, bottom) # %% Exercice 2 : Implémentation d'une file à l'aide de deux piles class file(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/""" def __init__(self, option=1): """ Crée une file vide. Option 1 pour être efficace sur pop mais lent sur push, option 2 l'inverse.""" self.p1 = creerPileVide() self.p2 = creerPileVide() self.option = option def push(self, x): """ 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). """ if self.option == 1: while not estVide(self.p1): y = pop(self.p1) push(self.p2, y) push(self.p1, x) while not estVide(self.p2): y = pop(self.p2) push(self.p1, y) elif self.option == 2: push(self.p1, x) else: raise ValueError("file.push(): option doit être 1 ou 2.") def pop(self): """ 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), """ if self.option == 1: return pop(self.p1) elif self.option == 2: if estVide(self.p2): while not estVide(self.p1): y = pop(self.p1) push(self.p2, y) return pop(self.p2) else: raise ValueError("file.push(): option doit être 1 ou 2.") def estVide(self): """ Teste si la file est vide (en O(1)).""" return estVide(self.p1) and estVide(self.p2) def hauteur(self): """ Calcule la hauteur n de la pile p (longueur), complexité O(n). - Ne modifie pas la pile p. """ return hauteur(self.p1) + hauteur(self.p2) def __repr__(self): """ Petite fonction pour afficher joliment notre file.""" return "f: p1 = %s, p2 = %s (option %i)" % (self.p1, self.p2, self.option) __str__ = __repr__ # %% Exercice 3 : Évaluation d'expressions arithmétiques postfixées if __name__ == '__main__': print("\n\nExercice 3 : exemples d'expressions :") expr1 = [1, 2, "+"] # 1 + 2 print("expr1 : 1 + 2 <->", expr1) expr2 = [1, 2, "-", 3, "+"] # (1 - 2) + 3 print("expr2 : (1 - 2) + 3 <->", expr2) expr3 = [1, 2, 3, "+", "-"] # 1 - (2 + 3) print("expr3 : 1 - (2 + 3) <->", expr3) expr4 = [1, 1, 2, "+", 5, 3, 8, "+", "-", "*", "-"] # 1 - (1+2) * (5 - (3+8)) print("expr4 : 1 - (1+2) * (5 - (3+8)) <->", expr4) # 3.1 def verifier(expr, verb=False): r""" 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. """ n = 0 for symbol in expr: if verb: print(" n =", n, "et symbole =", symbol) if isinstance(symbol, int) or isinstance(symbol, float): n += 1 elif isinstance(symbol, str): if symbol in ['+', '-', '*', '/', '//']: n -= 1 else: return False if n <= 0: return False return n == 1 if __name__ == '__main__': print("\nVérifions quelques expressions valides :") print(expr1, "est valide ?", verifier(expr1)) print(expr2, "est valide ?", verifier(expr2)) print(expr3, "est valide ?", verifier(expr3)) print(expr4, "est valide ?", verifier(expr4)) print("\nPlus de détails :") print(expr4, "est valide ?", verifier(expr4, verb=True)) print("\nVérifions quelques exercises invalides :") expr5 = [1, 2, "+", "*", 3] # 1 2 + * 3 print("1 2 + * 3 <-> ", expr5) print("expr5 =", expr5, "est valide ?", verifier(expr5)) expr6 = [1, 2, "+", 3, 4, "*"] # 1 2 + 3 4 * print("1 2 + 3 4 * <-> ", expr6) print("expr6 =", expr6, "est valide ?", verifier(expr6)) print("\nPlus de détails :") print(expr6, "est valide ?", verifier(expr6, verb=True)) # 3.2 def evaluer(expr, verb=False): """ É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). """ assert verifier(expr), "Impossible d'évaluer une expression invalide !" pileValeurs = [] for symbol in expr: if verb: print("\n pileValeurs =", pileValeurs) print(" Symbole lu =", symbol) if isinstance(symbol, int) or isinstance(symbol, float): pileValeurs.append(symbol) elif symbol == '+': a = pileValeurs.pop() b = pileValeurs.pop() c = b + a pileValeurs.append(c) elif symbol == '-': a = pileValeurs.pop() b = pileValeurs.pop() c = b - a # Attention à l'ordre ! pileValeurs.append(c) elif symbol == '*': a = pileValeurs.pop() b = pileValeurs.pop() c = b * a pileValeurs.append(c) elif symbol == '/': a = pileValeurs.pop() b = pileValeurs.pop() c = b / a # Attention à l'ordre ! pileValeurs.append(c) elif symbol == '//': a = pileValeurs.pop() b = pileValeurs.pop() c = b // a # Attention à l'ordre ! pileValeurs.append(c) # On a terminé assert len(pileValeurs) == 1 return pileValeurs[0] if __name__ == '__main__': print("\nÉvaluons quelques expressions valides :") print("expr1 : 1 + 2 vaut", evaluer(expr1), "(on attendait 3)") print("expr2 : (1 - 2) + 3 vaut", evaluer(expr2), "(on attendait 2)") print("expr3 : 1 - (2 + 3) vaut", evaluer(expr3), "(on attendait -4)") print("expr4 : 1 - (1+2) * (5 - (3+8)) vaut", evaluer(expr4), "(on attendait 19)") print("\nPlus de détails :") r = evaluer(expr4, verb=True) print("expr4 : 1 - (1+2) * (5 - (3+8)) vaut", r, "(on attendait 19)") # 3.3 if __name__ == '__main__': print("\n3.3.a) verifier et evaluer sont en O(n) : linéaires dans la longueur de l'expression.") print("\n3.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).") # 3.4 def evaluer_infixes(expr): """ Évaluation d'une expression infixe.""" print("TODO evaluer_infixes")