TD reduction chaine

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.

Pour les fonctions est_vide et depile, ajouter un test d’assertion pour lever les exceptions dans le cas où la pile est vide.
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 +

video notation polonaise inversée — Arnaud Bodin : Calculatrice polonaise - les piles

La liste L contient les caractères de l’expression POSTFIXE à calculer.

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]

Compléter les fonctions add, soust, et multip qui doivent additionner, soustraire, et multiplier les arguments x et y.
Testez vos fonctions à l’aide du tableau associatif: Executer en console l’instruction: dicoP['-'](3,4) qui doit renvoyer … -1
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

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é basique

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.

Testez votre fonction avec les arguments suivants:

reduction(['d','D','a','A','a'])
-> ['d','D','a']
reduction(['d','a','a','b','A','a','A','a'])
-> ['d','a','a','b']
reduction(['d','a','c','a','A','a','A','a','C'])
-> ['d', 'a', 'a', 'b']
reduction(['B','a','A','c','A','a','A','a','C','b'])
-> []

correction

Enoncé difficile

On modifie maintenant la règle du jeu: les motifs peuvent être réduits par groupe de 2, comme précédemment, mais aussi par groupe de 3 si ceux-ci présentent une alternance minuscule-majuscule-minuscule ou bien majuscule-minuscule-majuscule:

reduction(['b','D','a','A','a'])
-> ['b','D']
reduction(['d','D','a','A','a'])
-> ['d','D'] puis []
reduction(['b', 'D', 'a','a','A','a'])
-> ['b','D','a']

Par contre, il n’y aura pas de reduction lorsque la séquence ne présente pas d’alternance:

> reduction(['d','a','a','b','A','a','A','a'])
['d','a','a','b']