Exercice 1 : implementer une pile

On donne les fonctions qui implémentent la pile: Pile,est_vide,empile,depile,sommet:

L = ['a',1,'b',2,'c',3,'d',4]

def Pile():
    return []

def est_vide(pile):
    return pile == []

def depile(pile):
    return pile.pop()

def empile(a,pile):
    pile.append(a)

def sommet(pile):
    return pile[-1]

Utilisez les fonctions de cette interface pour resoudre l’exercice suivant:

* Soit une liste L = ["a",1,"b",2,"c",3,"d",4]
* Parcourir les éléments de la liste L avec une boucle bornée
* empiler tous les **nombres entiers** dans une pile `p`.
* afficher `p`

L = ['a',1,'b',2,'c',3,'d',4]

On pourra utiliser la fonction isinstance(a,int) qui retourne True si a est de type int.

Exercice 2 : lever des exceptions

Certaines des fonctions que vous avez écrites vont générer des erreurs dans le cas où la pile est vide.

1. Pour les fonctions est_vide et depile, ajouter un test d’assertion pour lever les exceptions dans le cas où la pile est vide.
2. Tester ces fonctions avec une pile vide.

Exercice 3 : déverser une pile

Déverser une pile

Ecrire une fonction deversepile qui déverse une pile p1 dans une pile p2.

Pour que p2 soit identique à p1, il faudra utiliser une pile intermédaire p3 de la manière suivante:

p1,p2,p3=Pile(),Pile(),Pile()
deversepile(p1,p3)
deversepile(p3,p2)

Les fonctions que vous pourrez utiliser pour les piles seront celles définies dans l’exercice 1 : Pile,est_vide,empile,depile,sommet.

Visualiser sur Pythontutor

Ouvrir l’editeur pythontutor et executer le script pas à pas.

Remarquez-vous?

• La pile p1 est-elle vide à la fin du dépilement?
• Les listes p1 et p2 sont-elles modifiées par effet de bord, dans la fonction?
• Les éléments se rangent-ils en sens inverse dans p2?

Exercice 4 : Evaluation d’une opération en notation polonaise inversée

Principe

la notation polonaise inversée permet d’écrire une opération sans utiliser de parenthèses. Il faut alors écrire les 2 opérandes avant l’opérateur. L’opérateur se trouve à droite des 2 opérandes.

En parcourant l’expression L de gauche à droite (boucle for):

• chaque fois que l’on rencontre un opérateur:

  • on dépile 2 fois la pile p pour rechercher les 2 opérandes (nombres)
  • on empile le resultat de l’opération.

• chaque fois que l’on rencontre un entier, on l’empile dans p

On peut utiliser une pile pour réaliser la séquence de calculs.

Exemple : 1 2 + 4 * 3 +

Problème simplifié: Opérations d’addition seulement

Dans un premier temps, on ne va considérer que des expressions contenant des entiers et l’opérateur +.

Par exemple, L = [7, 8, '+', 6, '+', 10, '+', 3, '+']

Cette expression sera évaluée à 34.

L = [7, 8, '+', 6, '+', 10, '+', 3, '+']

def Pile():
    return []

def est_vide(pile):
    return pile == []

def depile(pile):
    assert pile != [], 'impossible de depiler : pile vide'
    return pile.pop()

def empile(a,pile):
    pile.append(a)

def sommet(pile):
    assert pile != [], 'la pile n_a pas de sommet : pile vide'
    return pile[-1]

def evalNPI(L):
    """evalue l'expression postfixe de type 
    notation polonaise inversee
    :Params:
    L : list of str and int: liste contenant les caracteres et les nombres entiers
    :Returns:
    p[0]: int, le resultat de l'evaluation de L, seul element restant de la pile p
    :variables:
    p : list of int: les entiers stockés pour leur evaluation
    :Exemple:
    >>> evalNPI([7, 8, '+', 6, '+', 10, '+', 3, '+'])
    34
    """
    p=[]    
    # à completer #
    return p[0]

Calculatrice complète

On donne le script python à compléter:

L = [7, 8, '-', 6, '*', 10, 3, '+', '*']


def Pile():
    return []

def est_vide(pile):
    return pile == []

def depile(pile):
    assert pile != [], 'impossible de depiler : pile vide'
    return pile.pop()

def empile(a,pile):
    pile.append(a)

def sommet(pile):
    assert pile != [], 'la pile n_a pas de sommet : pile vide'
    return pile[-1]



def add(x,y):
    # à completer #

def soust(x,y):
    # à completer #

def multip(x,y):
    # à completer #

dicoP = {'+' : add,
        '-' : soust,
        '*' : multip
}


def evalNPI(L):
    """evalue l'expression postfixe de type 
    notation polonaise inversee
    :Params:
    L : list of str and int: liste contenant les caracteres et les nombres entiers
    :Returns:
    p[0]: int, le resultat de l'evaluation de L, seul element restant de la pile p
    :variables:
    p : list of int: les entiers stockés pour leur evaluation
    :Exemple:
    >>> evalNPI([7, 8, '-', 6, '*', 10, 3, '+', '*'])
    -78
    """
    p=[]    
    # à completer #
    return p[0]

1. Compléter les fonctions add, soust, et multip qui doivent additionner, soustraire, et multiplier les arguments x et y.
2. Testez vos fonctions à l’aide du tableau associatif: Executer en console l’instruction: dicoP['-'](3,4) qui doit renvoyer … -1
3. Compléter la fonction evalNPI: Dans une boucle bornée qui parcourt tous les éléments de la liste L: for a in L:

• si a est un entier: empiler a dans une liste p qui sera utilisée comme une pile.
• si a est un opérateur présent dans le tableau associatif dicoP:
  • depiler p deux fois et stocker les valeurs dans les opérandes x et y.
  • empiler la valeur calculée dans la pile p
• retourner la valeur finale stockée dans p

Variante utilisant les fonctions lambda

On peut racourcir l’écriture du script en utilisant des fonctions lambda. Elles utilisent des paramètres pour calculer une valeur de retour, comme une fonction. Elles ne peuvent contenir qu’une expression.

On les déclare de la manière suivante:

lambda arguments: expression

Exemple 1:

sum = lambda a,b : a+b

Ces fonctions peuvent ne pas être nommées. On les place alors dans une liste, ou un dictionnaire.

dico = {'+' : lambda x,y : x+y,
        '-' : lambda x,y : x-y,
        '*' : lambda x,y : x*y
        }

On calcule alors avec cette fonction en faisant: dico[a](3,4) par exemple:

Exemple 2:

a = '+'
if a == '+':
    r = dico[a](3,4)
    print(r)
# affiche 7

L’interêt des fonctions lambda est surtout de rendre le script plus lisible. Cela donne une autre option d’écriture.

Exercice 5 (Projet): Reduction d’une chaine de caractères

Enoncé à la page suivante

On utilisera pour cet exercice l’implementation d’un pile avec les definitions suivantes:

def Pile():
    return []

def est_vide(pile):
    return pile == []

def depile(pile):
    assert pile != [], 'impossible de depiler : pile vide'
    return pile.pop()

def empile(a,pile):
    pile.append(a)

def sommet(pile):
    assert pile != [], 'la pile n_a pas de sommet : pile vide'
    return pile[-1]

Enoncé difficile

Certains jeux comme par exemple Candie Crush reposent sur l'élimination de motifs adjacents. Je vous propose ici d’utiliser une chaine de caractères dans laquelle les motifs vont être éliminé de la manière suivante:

Programmez la fonction reduction qui va permettre de réaliser ceci.

On se limitera aux caractères ‘a’, ‘A’, ‘b’, ‘B’, ‘c’, ‘C’, ’d', ‘D’ pour cette chaine.

Enoncé progressif

On va chercher un solution qui ressemble à celle de la notation polonaise inversée, utilisant une Pile.

On donne 2 fonctions qui seront utiles pour la resolution:

def deversePile(pile1,pile2):
    while not est_vide(pile1):
        empile(depile(pile1),pile2)
        
def motif(pile):
    p2 = Pile()
    i = 0
    if not est_vide(pile):
        c1 = depile(pile)
        empile(c1,p2)
    while not est_vide(pile) and sommet(pile) in dicoS and c1 == dicoS[sommet(pile)]:
        c2 = depile(pile) # c2 est le sommet
        empile(c2,p2)
        i = i + 1
        c1 = c2
    deversePile(p2,pile)
    #return i, p2, pile
    return i

Partie 1: fonction motif(pile)

cette fonction retourne le nombre de motifs consecutifs comptés à partir du sommet de la pile:

Pour [‘z’,‘a’,‘a’,‘A’,‘a’]

• la fonction compte un motif pour [‘z’,‘a’,‘a’,‘A’,‘a’]
• puis un motif pour [‘z’,‘a’,‘a’,‘A’,‘a’]

Ce qui fait 2 motifs consécutifs.

Testez la fonction avec les arguments suivants:

> motif(['z','a','a','A','a'])
> motif(['z','a','a','b','A','a','A','a'])
> motif(['z','a','c','a','A','a','A','a','C'])
> motif(['z','a','c','a','A','a','A','a','C'])

Partie 2: fonction recursive destruction_pile

def destruction_recur(pile):
    if motif(pile) == 0:
      # a completer
    else:
        return destruction_recur(pile[:-1])

Completer la fonction destruction_pile avec pour paramètre pile.

Les 2 conditions d’arrêt seront:

• retourne pile si le nombre de motifs à partir du sommet est égal à zero
• retourne pile dont on supprime les 2 éléments du sommet si le nombre de motifs à partir du sommet est égal à 1
• appel recursif avec pour argument pile dont on a supprimé l’élément du sommet.

Completer le script et tester la fonction avec les différents exemples de piles donnés plus haut.

Partie 3: fonction simplifier Dans la fonction simplifier:

• on utilise un dictionnaire pour mettre les caractères en correspondance ‘a’ : ‘A’, …
• on parcours chaque caractères c d’une chaine s
• on utilise une pile pour stocker des caractères au fur et à mesure du parcours de s
• si p n’est pas vide, si le caractere au sommet de la pile p est une clé du dictionnaire dicoS, et si ce caractère correspond à c selon la regle établie pour l’énoncé du problème (‘a’ : ‘A’, …):
• empiler c dans p
• sinon si p non vide, mais c et le sommet de p ne correspondent pas:
• appel recursif de destruction_recur
• empiler c dans p
• nouvel appel recursif de destruction_recur
• sinon: empiler c dans p

def simplifier(s):
    dicoS = {'a':'A','b':'B','c':'C','d':'D','A':'a','B':'b','C':'c','D':'d'}
    p = Pile()
    for c in s:
        ...