Exemple : calculatrice RPN

Principe

Calculatrice RPN

Principe : un calcul est effectué à l’aide d’une pile

Les nombres rentrés par l’utilisateur sont stockés dans une pile (empilés les uns sur les autres), et lorsqu’on fait une opération, on reprend de la pile les éléments nécessaires à l’opération, et on remet ensuite le résultat dans la pile.

Exemple : http://www.poleyland.com/hp48/

Opérations

Pour réaliser ce genre d’outil, on a besoin de pouvoir mettre des chiffres dans une pile : le dernier nombre rentré est le premier qu’on peut récupérer : LIFO : Last In First Out

On doit pouvoir réaliser les opérations suivante sur une pile (spécification) :

créer une pile : newpile() ou Pile() -> pile
rajouter un élément dans la pile : empile(pile, elt) -> None ou pile.empile(elt) -> None
récupérer le dernier élément de la pile (et le supprimer de la pile par la même occasion) : depile(pile) -> nombre (erreur si la pile est vide), ou bien pile.depile() -> nombre (pour une pile objet)
renvoyer le nombre d’éléments dans la pile nbelts(pile) -> nombre, ou len(pile) -> nombre (pour une pile objet)

La manière exacte de réaliser ces opérations est réalisée lors de l’implémentation.

Implémentation d’une pile

Implémentation avec une liste

Programme

def newpile():
    return list()

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

def depile(pile):
    assert len(pile) > 0, "Pile vide"
    return pile.pop()

def nbelts(pile):
    return len(pile)

Tests

## Test de cette implémentation
pile = newpile()
empile(pile, 1)
empile(pile, 2)
assert nbelts(pile) == 2, pile
assert depile(pile) == 2, pile
assert nbelts(pile) == 1, pile
assert depile(pile) == 1, pile
assert nbelts(pile) == 0, pile
try:
    depile(pile)
    print("Une erreur aurait dû avoir lieu")
except AssertionError:
    pass

Implémentation pile 2

Via un objet et une liste

class Pile():
    def __init__(self):
        self.__liste = []
    def empile(self, elt):
        self.__liste.append(elt)
    def depile(self):
        assert len(self.__liste) > 0, "Pile vide"
        return self.__liste.pop()
    def nbelts(self):
        return len(self.__liste)
    def __str__(self):
        return str(self.__liste)
    def __len__(self):
        return len(self.__liste)

Tests

## Test de cette implémentation
pile3 = Pile()
pile3.empile(1)
pile3.empile(2)
assert str(pile3) == "[1, 2]"
assert pile3.nbelts() == 2
assert len(pile3) == 2
assert pile3.depile() == 2
assert pile3.nbelts() == 1
assert pile3.depile() == 1
assert pile3.nbelts() == 0

try:
    pile3.depile()
    print("Une erreur aurait dû avoir lieu")
except AssertionError:
    pass

Spécification d’une structure de données

A retenir

Spécification

Lorsqu’on veut développer un programme, il faut le plus vite possible identifier et spécifier les structures de données.

Une spécification est une définition formelle du comportement d’une certaine structure de données.

c’est un contrat entre l’utilisateur et la personne qui va développer (implémenter) la structure de données
elle dit ce que doit faire la structure de données
elle ne dit pas comment le faire (implémentation)
elle doit être précise et rigoureuse
elle doit éviter de poser des contraintes d’implémentation

File

Principe

File

Une file est une structure de données qui permet de stocker des éléments dans un ordre précis : le premier élément entré est le premier élément sorti (FIFO : First In First Out).

Spécification et implémentation(s)

Spécification

En vous inspirant de la spécification de la pile, écrivez la spécification d’une file et écrivez les tests permettant de la vérifier, pour une pile implémentée sous forme de fonctions, puis sous forme d’objet.

Implémentation

en vous inspirant de l’implémentation de la pile, écrivez une implémentation d’une file de manière fonctionnelle (info utile : pop() prend aussi un argument index pour sortir un élément à un index donné, en particulier 0 pour sortir le premier élément).
en vous inspirant de l’implémentation de la pile, écrivez une implémentation d’une file de manière objet.

Mini projet

Calculatrice RPN

A faire

Ecrire une fonction rpn(pile, actions) prenant comme arguments une pile pile et une chaîne de caractères actions, qui réalise les opérations contenues dans action sur la pile pile.

Ecrire les assertions permettant de vérifier le bon fonctionnement de la calculatrice.

Exemples

pile vide, actions = “2 2 + 3 *” : réalise les actions “empiler 2”, “empiler 2”, “depiler deux valeurs, les additionner et empiler le résultat”, “empiler 3”, “dépiler deux valeurs, les multiplier et empiler le résultat”. La pile contient donc à la fin un seul nombre : 12
pile contenant 2 (bas) et 3 (haut), actions = “/ 1 +” : réalise les action “dépiler deux valeurs, les diviser (3/2) et remettre le résultat dans la pile”, “empiler 1”, “dépiler deux valeurs, les additionner et remettre le résultat dans la pile”. La pile contient donc à la fin un seul nombre : 2,5.

Actions possibles : +,-,*,/,^ ou **, cos, sin, tan, dup (dupliquer le dernier élément), swap (échanger les deux derniers éléments de la pile) et drop (supprimer le dernier élément de la pile)

Indications

actions.split(" ") permet de couper une chaîne de caractères à chaque espace pour la transformer en liste
float(str) permet de transformer une chaîne de caractères en nombre, en levant une exception ValueError si le nombre est invalide
depuis 2021, le python a une structure de contrôle match/case qui peut remplacer des suites de elif (ce qui ne veut pas dire que c’est à utiliser forcément ici) :

command = 'Hello, World!'
match command:
 case 'Hello, World!':
     print('Hello to you too!')
 case 'Goodbye, World!':
     print('See you later')
 case other:
     print('No match found')