class Node:
def __init__(self, valeur, suivant: 'Node' =None):
self.valeur = valeur
self.suivant = suivant
class Liste:
def __init__(self, head: Node):
self.head = head
def __str__(self) -> str:
return "(" + ",".join(map(lambda e: str(Liste(e) if isinstance(e, Node) else e),
self.to_list())) + ")"
def to_list(self) -> list:
if self.head is None:
return []
return [self.head.valeur] + self.cdr().to_list()
def __len__(self) -> int:
"""Longueur de la liste.
"""
if self.head is None:
return 0
return 1 + len(self.head.suivant)
def append(self, valeur) -> None:
"""Ajouter une valeur à la fin de la liste.
"""
# cas de base :
# on doit s'arrêter dès que la liste est terminer
if self.head.suivant is None:
# on créé un nouveau Node
self.head.suivant = Node(valeur)
# récursion pour atteindre la fin de la liste
self.cdr().append(valeur)
def car(self):
"""Récupérer la valeur en tête de liste
"""
return self.head.value
def cdr(self) -> 'Liste':
"""Récupérer la liste sans son premier élément.
"""
if self.head is None:
return None
return Liste(self.head.suivant)
def last(self):
"""Récupérer le dernier élément de la liste.
"""
if self.head.suivant is None:
return self.last(Liste(self.head.suivant))
return self.head.valeur
1 Bégaie - De bégaie
On dit qu’une liste est “bégayée” lorsque chaque élément y apparaît deux fois de suite. Le but de cet exercice est de transformer une liste en une liste bégayée, et inversement de “dé bégayer” une liste en supprimant un élément sur deux.
1.1 Bégaie
1.1.1 Fonction itérative
écrire la fonction itérative
begaie
qui, étant donnée une liste d’éléments, renvoie la liste où chaque élément est répété. Par exemple :begaie(1,2,3,1,4) = (1,1,2,2,3,3,1,1,4,4)
etbegaie(None) = None
.
def begaie(L: Node) -> Node:
= L
p while p is not None:
# insérer un mode contenant la même valeur
= Node(p.valeur, p.suivant)
tmp = tmp
p.suivant # on passe au pointeur suivant
= p.suivant.suivant
p return L
On peut tester :
= Node(3, Node(1, Node(4, Node(1, Node(5, Node(9))))))
L print(Liste(L))
print(Liste(begaie(L)))
(3,1,4,1,5,9)
(3,3,1,1,4,4,1,1,5,5,9,9)
Et on a bien :
print(begaie(None))
None
1.1.2 Fonction récursive
Donner maintenant une fonction récursive
begaieRec
qui effectue le même traitement que la fonctionbegaie
précédente
def begaieRec(L: Node) -> Node:
if L is None:
return None
return Node(L.valeur, Node(L.valeur, begaieRec(L.suivant)))
Elle fonctionne également :
= Node(3, Node(1, Node(4, Node(1, Node(5, Node(9))))))
L print(Liste(L))
# La fonction modifie la valeur de L, donc on pourrait
# simplement appeler la fonction, sans modifier
# explicitement L (sans mettre le `L = `)
= begaie(L) L
(3,1,4,1,5,9)
1.2 Dé bégaie
1.2.1 Fonction itérative
Écrire maintenant la fonction itérative
debegaie
qui prend en argument une liste bégayée et retourne la liste privée de ses doublons. La fonction de bégaie est telle quedebegaie(begaie(L)) = L
def debegaie(L: Node) -> Node:
if L is None:
return None
= L
p # on est obligé
while p.suivant.suivant is not None:
= p.suivant.suivant
p.suivant = p.suivant
p # on retire le dernier élément
# p.suivant = None
return L
= Node(3, Node(1, Node(4, Node(1, Node(5, Node(9))))))
L = begaie(L)
L print(Liste(L))
= debegaie(L)
L print(Liste(L))
(3,3,1,1,4,4,1,1,5,5,9,9)
(3,1,4,1,5,9,9)
1.2.2 Fonction récursive
Écrire enfin la fonction récursive
debegaieRec
qui réalise le même traitement que la fonctiondebegaie
.
def debegaieRec(L: Node) -> Node:
# cas de base
if L is None:
return None
# on doit ajouter ce cas de base car on utilise
# L.suivant.suivant, donc L.suivant ne doit pas être None
if L.suivant is None:
return None
# On créée une nouvelle liste qui saute un élément
return Node(L.valeur, debegaieRec(L.suivant.suivant))
= Node(3, Node(1, Node(4, Node(1, Node(5, Node(9))))))
L = begaie(L)
L print(Liste(L))
= debegaie(L)
L print(Liste(L))
(3,3,1,1,4,4,1,1,5,5,9,9)
(3,1,4,1,5,9,9)
2 Implémentation de la fonction zip
De très nombreux langages de programmations permettent de travailler sur des structures de listes chaînées. Le langage Python notamment permet de travailler nativement avec les listes et implémente la fonction zip(l1, l2)
qui permet, à partir de 2 listes de même longueur de construire une liste contenant les couples de valeurs formés des éléments de même indice issu des 2 listes. Par exemple :
= zip((1, 2, 3), ("a", "b", "c" ))
Z print(list(Z))
[(1, 'a'), (2, 'b'), (3, 'c')]
2.1 Itérative
- Écrire la fonction itérative zip(l1, l2) qui permet d’obtenir le résultat désiré en suivant le formalisme des listes chaînées étudiées en cours. On supposera les listes en argument de même taille et non vides.
def zip_iter(L1: Node, L2: Node) -> Node:
= L1
p = L2
q = None
res = None
last while p is not None and q is not None:
if res is None:
= Node(Node(p.valeur, Node(q.valeur)))
res = res
last else:
= Node(Node(p.valeur, Node(q.valeur)))
last.suivant = last.suivant
last = p.suivant
p = q.suivant
q return res
= Node(3, Node(1, Node(4, Node(1, Node(5, Node(9, Node(2)))))))
L1 = Node(1, Node(6, Node(1, Node(8, Node(0, Node(3, Node(3)))))))
L2 print(Liste(zip_iter(L1, L2)))
print(Liste(L1), Liste(L2))
((3,1),(1,6),(4,1),(1,8),(5,0),(9,3),(2,3))
(3,1,4,1,5,9,2) (1,6,1,8,0,3,3)
2.2 Récursive
- Produire une solution récursive équivalente.
def zip_rec(L1: Node, L2: Node) -> Node:
if L1 is None or L2 is None:
return None
return Node(Node(L1.valeur, Node(L2.valeur)),
zip_rec(L1.suivant, L2.suivant))
= Node(3, Node(1, Node(4, Node(1, Node(5, Node(9, Node(2)))))))
L1 = Node(1, Node(6, Node(1, Node(8, Node(0, Node(3, Node(3)))))))
L2 = Node(1, Node(2, Node(3)))
L3 print(Liste(zip_rec(L1, L2)))
print(Liste(zip_rec(L1, L3)))
((3,1),(1,6),(4,1),(1,8),(5,0),(9,3),(2,3))
((3,1),(1,2),(4,3))
3 Liste croissante
On considère dans cet exercice une liste contenant des valeurs comparables grâce à l’opérateur <=
.
3.1 Itérative
- Écrire la fonction itérative
croissante(L)
qui prend en argument une telle liste et retourneTrue
si et seulement si la liste est triée par ordre croissant au sens large.
On implémentera la fonction en considérant les cas de base suivants : - une liste vide est considérée comme triée par ordre croissant - une liste avec un seul élément est croissante également
def croissante_iter(L: Node) -> bool:
if L is None: return True
= L
p while p.suivant is not None:
# si deux éléments sont dans un ordre décroissant
if p.valeur > p.suivant.valeur:
# on sait que la liste n'est pas croissante
return False
= p.suivant
p # si on a trouvé aucune valeur décroissante dans la liste, on sait qu'elle
# est croissante
return True
= Node(1, Node(6, Node(6, Node(42, Node(73)))))
L print(croissante_iter(L)) # True
= Node(1, Node(6, Node(0, Node(42))))
L print(croissante_iter(L)) # False
True
False
3.2 Récursive
- Proposer une solution récursive.
def croissante_rec(L: Node) -> bool:
if L is None: return True
if L.suivant is None: return True
# si les valeurs en tête sont décroissantes
if L.valeur > L.suivant.valeur:
return False
return croissante_rec(L.suivant)
= Node(1, Node(6, Node(6, Node(42, Node(73)))))
L print(croissante_iter(L)) # True
= Node(1, Node(6, Node(0, Node(42))))
L print(croissante_iter(L)) # False
True
False
4 Suppression des occurrences d’un élément
Nous nous intéressons maintenant à la suppression d’un élément quelconque dans une liste chaînée.
4.1 Itérative
- Écrire une fonction itérative
removeAll(L, elem)
qui prend en argument une liste chaînéeL
et une valeurelem
et retourne la liste privée de ses élémentselem
.
def remove_all_iter(L: Node, elem) -> Node:
if L is None: return None
# on cherche la première valeur
while L.valeur == elem:
= L.suivant
L # si on a passé toutes les valeurs, c'est que la liste ne contient que
# des valeurs à supprimer :
if L is None: return None
= Node(L.valeur)
res = res
res_tl while L is not None:
if L.valeur != elem:
= Node(L.valeur)
res_tl.suivant = res_tl.suivant
res_tl = L.suivant
L return res
print("Liste vide :", remove_all_iter(None, 9))
= Node(42, Node(42, Node(42, Node(42, Node(42, Node(42, Node(42)))))))
L print("Liste à supprimer complètement :",
42)))
Liste(remove_all_iter(L,
= Node(73, Node(73, Node(73, Node(42, Node(42)))))
L print("Liste qui commmence par les éléments à supprimer :",
73)))
Liste(remove_all_iter(L,
= Node(1, Node(1, Node(1, Node(8, Node(1, Node(3, Node(3)))))))
L print("Liste mixte :",
1))) Liste(remove_all_iter(L,
Liste vide : None
Liste à supprimer complètement : ()
Liste qui commmence par les éléments à supprimer : (42,42,42)
Liste mixte : (8,8,3,3)
4.2 Récursive
- Proposer une solution récursive à ce problème. Indications : pensez à différencier les cas suivants :
- la liste est vide initialement,
- la liste ne contient que l’élément à supprimer,
- la liste commence par les éléments à supprimer,
- la liste est mixte : composée pour une part de l’élément à supprimer et pour une autre part d’autres éléments à conserver.
def remove_all(L: Node, elem) -> Node:
if L is None: return None
if L.valeur == elem:
return remove_all(L.suivant, elem)
return Node(L.valeur, remove_all(L.suivant, elem))
print("Liste vide :", remove_all_iter(None, 9))
= Node(42, Node(42, Node(42, Node(42, Node(42, Node(42, Node(42)))))))
L print("Liste à supprimer complètement :",
42)))
Liste(remove_all_iter(L,
= Node(73, Node(73, Node(73, Node(42, Node(42)))))
L print("Liste qui commmence par les éléments à supprimer :",
73)))
Liste(remove_all_iter(L,
= Node(1, Node(1, Node(1, Node(8, Node(1, Node(3, Node(3)))))))
L print("Liste mixte :",
1))) Liste(remove_all_iter(L,
Liste vide : None
Liste à supprimer complètement : ()
Liste qui commmence par les éléments à supprimer : (42,42,42)
Liste mixte : (8,8,3,3)
5 Suite de Fibonacci
La suite de Fibonacci est définie comme suit :
- \(f_0 = 1\)
- \(f_1 = 1\)
- \(f_n = f_{n-1} + f_{n-2}\) si \(n > 1\)
5.1 Itérative
- Écrire la définition de la fonction itérative
fibonacci(n)
qui, étant donné un entier natureln
renvoie la liste \((f_n, f_{n−1}, f_{n−2}, \ldots, f_1, f_0)\) où les fi sont les termes de la suite de Fibonacci.
Par exemple :
0) = (1)
fibonacci(1) = (1, 1)
fibonacci(4) = (1, 1, 2, 3, 5)
fibonacci(5) = (1, 1, 2, 3, 5, 8) fibonacci(
def fibonacci(n: int) -> Node:
if n == 0:
return Node(1)
= Node(1, Node(1))
res # on a déjà fait la 1ère étape en définissant res, donc on peut diminuer n
-= 1
n # _ est un nom de variable que l'on utilise quand on sait que l'on ne va
# pas utiliser cette variable.
for _ in range(n):
# somme de la dernière et l'avant dernière valeur
= Node(res.valeur + res.suivant.valeur, res)
res return res
for n in range(10):
print(f"fibonacci({n}) = {Liste(fibonacci(n))}")
fibonacci(0) = (1)
fibonacci(1) = (1,1)
fibonacci(2) = (2,1,1)
fibonacci(3) = (3,2,1,1)
fibonacci(4) = (5,3,2,1,1)
fibonacci(5) = (8,5,3,2,1,1)
fibonacci(6) = (13,8,5,3,2,1,1)
fibonacci(7) = (21,13,8,5,3,2,1,1)
fibonacci(8) = (34,21,13,8,5,3,2,1,1)
fibonacci(9) = (55,34,21,13,8,5,3,2,1,1)
5.2 Récursive
- Produire une version récursive de cette fonction
def fibonacci_rec(n: int) -> Node:
if n == 0:
return Node(1)
if n == 1:
return Node(1, Node(1))
= fibonacci_rec(n - 1)
recursion return Node(recursion.valeur + recursion.suivant.valeur,
recursion)
for n in range(10):
print(f"fibonacci({n}) = {Liste(fibonacci(n))}")
fibonacci(0) = (1)
fibonacci(1) = (1,1)
fibonacci(2) = (2,1,1)
fibonacci(3) = (3,2,1,1)
fibonacci(4) = (5,3,2,1,1)
fibonacci(5) = (8,5,3,2,1,1)
fibonacci(6) = (13,8,5,3,2,1,1)
fibonacci(7) = (21,13,8,5,3,2,1,1)
fibonacci(8) = (34,21,13,8,5,3,2,1,1)
fibonacci(9) = (55,34,21,13,8,5,3,2,1,1)
6 interclassement
On s’intéresse dans cet exercice à deux méthodes d’interclassement de listes. L’interclassement vise à parcourir deux listes en parallèle et, à chaque itération, à insérer un élément venant de l’une ou de l’autre liste, dans la liste résultat. Le critère utilisé pour choisir la liste qui fournit l’élément à insérer suivant définit le type d’interclassement.
6.1 Interclassement strict
- On s’intéresse tout d’abord à un interclassement strict qui insère alternativement un élément de la première liste puis un élément de la seconde liste. Dans le cas où une liste est plus courte que l’autre, les éléments restants de la plus longue sont insérés à la fin de la liste résultat sans interclassement. Plus précisément, si une liste est vide dès le début, la seconde est retournée. Si les deux listes sont vides, alors la liste vide (None) est retournée. Par exemple :
On commence par créer une fonction qui permet de copier une liste chaînée (créer une nouvelle liste qui contien les mêmes valeurs).
def copy(L: Node) -> Node:
"""Créer une copie d'une liste chaînée."""
if L is None: return None
return Node(L.valeur, copy(L.suivant))
6.1.1 Itératif
def inter_strict_iter(L1: Node, L2: Node) -> Node:
if L1 is None: return copy(L2)
if L2 is None: return copy(L1)
= Node(L1.valeur, Node(L2.valeur))
res = L1.suivant
L1_p = L2.suivant
L2_p = res.suivant
res_tail while L1_p is not None and L2_p is not None:
= Node(L1_p.valeur, Node(L2_p.valeur))
res_tail.suivant = res_tail.suivant.suivant
res_tail = L1_p.suivant
L1_p = L2_p.suivant
L2_p if L1_p is None: res_tail.suivant = copy(L2_p)
if L2_p is None: res_tail.suivant = copy(L1_p)
return res
= Node(2, Node(6, Node(42, Node(73, Node(1237)))))
L1 = Node(0, Node(1, Node(0)))
L2 print(Liste(inter_strict_iter(L1, L2)))
(2,0,6,1,42,0,73,1237)
6.1.2 Récursif
def inter_strict_rec(L1: Node, L2: Node) -> Node:
if L1 is None or L2 is None: return None
return Node(L1.valeur, Node(L2.valeur,
inter_strict_rec(L1.suivant, L2.suivant)))
= Node('A', Node('B', Node('C', Node('D', Node('E')))))
L1 = Node(0, Node(1, Node(2)))
L2 print(Liste(inter_strict_iter(L1, L2)))
(A,0,B,1,C,2,D,E)
6.2 Interclassement croissant
- On considère maintenant deux listes de nombres
L1
etL2
qui sont triées par ordre croissant. Écrire une fonction d’interclassementinterCroissant(L1, L2)
qui insère à chaque itération l’élément le plus petit qui se trouve en tête de liste soit deL1
soit deL2
. Un tel interclassement produit une liste fusionnée elle-même triée par ordre croissant. Proposer une solution itérative puis une solution récursive à ce problème.
6.2.1 Itératif
def inter_croissant_iter(L1: Node, L2: Node) -> Node:
if L1 is None: return copy(L2)
if L2 is None: return copy(L1)
= L1
L1_p = L2
L2_p # init 1ère valeur
= None
res if L1_p.valeur < L2_p.valeur:
= Node(L1_p.valeur)
res = L1_p.suivant
L1_p else:
= Node(L2_p.valeur)
res = L2_p.suivant
L2_p = res
res_tail while L1_p is not None and L2_p is not None:
if L1_p.valeur < L2_p.valeur:
= Node(L1_p.valeur)
res_tail.suivant = res_tail.suivant
res_tail = L1_p.suivant
L1_p else:
= Node(L2_p.valeur)
res_tail.suivant = res_tail.suivant
res_tail = L2_p.suivant
L2_p if L1_p is None:
= copy(L2_p)
res_tail.suivant elif L2_p is None:
= copy(L1_p)
res_tail.suivant return res
= Node(1, Node(6, Node(42, Node(73, Node(1237)))))
L1 = Node(0, Node(12, Node(37, Node(67, Node(68)))))
L2 print(Liste(inter_croissant_iter(L1, L2)))
(0,1,6,12,37,42,67,68,73,1237)
6.2.2 Récursif
def inter_croissant_rec(L1: Node, L2: Node) -> Node:
match (L1, L2):None) | (None, L): return copy(L)
case (L, if L1.valeur < L2.valeur:
case (L1, L2) return Node(L1.valeur,
inter_croissant_rec(L1.suivant, L2))case other:
return Node(L2.valeur,
inter_croissant_rec(L1, L2.suivant))
= Node(1, Node(6, Node(42, Node(73, Node(1237)))))
L1 = Node(0, Node(12, Node(37, Node(67, Node(68)))))
L2 print(Liste(inter_croissant_iter(L1, L2)))
(0,1,6,12,37,42,67,68,73,1237)
7 Calculatrice
Nous nous intéressons à la conception d’une calculatrice qui repose sur une représentation des opérations à l’aide d’une pile. De façon à mener à bien ce programme, il va donc falloir - implémenter les fonctions de la barrière d’abstraction de la structure pile de données (push, pop), - comprendre la notation postfixée pour la saisie des opérations
De manière traditionnelle, les opérations sont notées de manière infixée avec, dans le cas d’un opérateur binaire, le placement de l’opérateur entre les 2 opérandes. On obtient la notation suivante : De manière traditionnelle, les opérations sont notées de manière infixée avec, dans le cas d’un opérateur binaire, le placement de l’opérateur entre les 2 opérandes. On obtient la notation suivante : \[\text{opérande}_1 \text{opérateur} \text{opérande}_2\]
comme par exemple : \(3 + 4\), \(2.5 / 3.14 \ldots\)
En notation postfixée, l’opérateur succède à son (dans le cas d’un opérateur unaire) ou ses (dans le cas d’un opérateur binaire) opérande(s).
Ainsi : “\(3+4\)” s’écrit en postfixe “\(3 4 +\)”.
L’intérêt d’une telle représentation est de pouvoir ensuite utiliser une pile pour réaliser les calculs en suivant le schéma de résolution suivant :
- si la pile ne contient qu’une valeur réelle, il s’agit du résultat du calcul,
- sinon on empile les valeurs réelles lorsqu’elles sont lues en entrée,
- si on lit un caractère correspondant à un opérateur binaire on dépile les deux dernières valeurs réelles, on effectue le calcul et on empile le résultat,
- si on lit un caractère correspondant à un opérateur unaire, comme l’opérateur de négation, on dépile la dernière valeur, on applique l’opérateur et on empile le résultat.
Attention : la division est une loi non commutative, c’est-à-dire que \(x/y \neq y/x\). Il faut donc garder à l’esprit qu’en écrivant “\(x y /\)” en postifixé, l’opération souhaitée est \(\frac{x}{y}\) mais que du fait de l’utilisation d’une pile, la valeur de \(y\) sera dépilée avant celle de \(x\) (pile = dernier arrivé, premier sorti).
Dans le cadre de notre programme, les opérateurs suivants doivent être reconnus :
+
: addition,-
: soustraction,*
: multiplication,/
divisionn
: négation
Similairement, on veillera à bien gérer les erreurs :
• soit de division par 0, • soit de dépilement de valeur inexistante : par exemple, essayer de dépiler les deux opérandes d’un opérateur +
alors qu’il n’y en a qu’un seul dans la pile
7.1 Notation postfixée
Indiquer la traduction en notation postfixée des expressions suivantes exprimées en notation infixée (les parenthèses ne sont là que pour vous aider à comprendre la priorité des opérations) :
(2 + 4) * n 5
2 4 + 5 n *
ou bien5 n 2 4 + *
9 / (3.5 + 6)
9 3.5 6 + /
(3 - 5) / (3 + 5)
3 5 - 3 5 + /
7.2 Caculatrice
- Implémenter une calculatrice simple en notation postfixée sur la base d’une pile gérée par votre barrière d’abstraction.
7.2.1 Pile
7.2.1.1 Push
def push(L: Node, valeur) -> Node:
return Node(valeur, L)
= Node(1, Node(2))
A = push(A, 42)
A print(Liste(A))
(42,1,2)
7.2.1.2 Get
def get(L: Node) -> Node:
if L is None:
return None
return L.valeur
print(Liste(A))
print(get(A))
(42,1,2)
42
7.2.1.3 Pop
def pop(L: Node) -> Node:
if L is None:
raise ValueError("pop from empty stack.")
return L.suivant
print(Liste(A))
= pop(A)
A print(Liste(A))
(42,1,2)
(1,2)
7.2.1.4 Is empty
def is_empty(L: Node) -> bool:
return L is None
print(is_empty(None))
print(is_empty(Node(1, Node(2))))
True
False
7.2.1.5 Height
def height(L: Node) -> int:
if is_empty(L):
return 0
return 1 + height(L.suivant)
= Node(1, Node(2, Node(3, Node(42))))
L print(height(L))
4
7.2.2 Abstraction de la calculatrice
On créée d’abord une fonction qui permet d’appliquer un opérateur binaire à une pile (sur les deux premiers éléments).
def appliquer(bin_operator, L: Node) -> Node:
"""Appliquer `bin_operator` sur les deux premières valeurs de la pile.
Le premier paramètre donné à `bin_operator` est le dessus de la pile, et le
second est le second élément de la pile.
"""
if L is None:
raise ValueError("applying operator on empty stack")
if L.suivant is None:
raise ValueError("applying operator on stack with only one element")
return Node(bin_operator(L.valeur, L.suivant.valeur), L.suivant.suivant)
= get(L)
first = pop(L)
L = get(L)
second = pop(L)
L = bin_operator(first, second)
result return push(result, L)
= Node(3, Node(2, Node(4, Node(1, Node(5)))))
A = lambda x, y: x+y
add = lambda x, y: y / x
div = appliquer(add, A)
A print(Liste(A))
= appliquer(div, A)
A print(Liste(A))
(5,4,1,5)
(0.8,1,5)
7.2.2.1 Opérateurs de base
def add(L: Node) -> Node:
return appliquer(lambda x, y: x+y, L)
def sub(L: Node) -> Node:
return appliquer(lambda x, y: y - x, L)
def mult(L: Node) -> Node:
return appliquer(lambda x, y: x * y, L)
def div(L: Node) -> Node:
return appliquer(lambda x, y: y / x, L)
= Node(3, Node(2, Node(1, Node(1, Node(5)))))
A print(Liste(A))
= add(A)
A print(Liste(A))
= sub(A)
A print(Liste(A))
= div(A)
A print(Liste(A))
= mult(A)
A print(Liste(A))
(3,2,1,1,5)
(5,1,1,5)
(-4,1,5)
(-0.25,5)
(-1.25)
7.2.2.2 Opérations unaires
Les opérations unaires sont des opérations qui modifient uniquement le premier élément de la pile.
def appliquer_unaire(operation, L: Node) -> Node:
if L is None:
raise ValueError("cannot apply unary function to an empty stack")
= get(L)
val = pop(L)
L return push(operation(val), L)
Voici quelques opérations unaires utiles :
def neg(L: Node) -> Node:
"""Négation : transformer la première valeur de la pile en son opposé.
"""
return appliquer_unaire(lambda x: -x, L)
def inv(L: Node) -> Node:
"""Inversion : inverser le premier élément de la pile (l'inverse de x est 1/x).
"""
return appliquer_unaire(lambda x: 1/x, L)
print(Liste(A))
= neg(A)
A print(Liste(A))
= inv(A)
A print(Liste(A))
7.2.2.3 Affichage d’une pile
On veut afficher la pile avec la tête en base, pour que les nombres les plus récents soient plus près de l’entrée utilisateur.
def stack_to_list(L: Node) -> list:
if L is None: return []
return [L.valeur] + stack_to_list(L.suivant)
def show_stack(L: Node) -> None:
# pour afficher la liste la tête en bas, on retourne la liste
print(*reversed(stack_to_list(L)), sep='\n')
= Node(1, Node(2, Node(3, Node(4, Node(5)))))
L show_stack(L)
7.2.2.4 Traduction des commandes
On veut créer une fonction qui transforme une liste selon une chaîne de caractères donnée, qui représente l’opération voulue.
On pourrait utiliser des structures if ... elif ... elif ... else
, ainsi que des clauses or
pour tester les différentes commandes, mais la structure match
(apparue dans la version 3.10 de python) permet une syntaxe plus claire, et des expressions plus riches.
from math import *
= ("exp" | "log" | "sqrt" | "ceil" | "floor" | "cos" | "sin" | "tan" | "cosh" | "sinh" | "tanh" | "acos" | "asin" | "atan")
FUNCS def appliquer_str(op_str: str, L: Node) -> Node:
"""Appliquer l'opération désignée par `op_str` sur `L`.
Exemples :
>>> appliquer_str("+", Node(1, Node(2))) # donne Node(3)
>>> appliquer_str("/", Node(5, Node(2))) # donne Node(0.4)
"""
match op_str:
case "+" | "add":
return add(L)
case "-" | "sub" | "subs":
return sub(L)
case "*" | "mul" | "mult" | "times":
return mult(L)
case "/" | "÷" | "div" | "divide":
return div(L)
case "-" | "neg" | "negate" | "oppose" | "opposite":
return neg(L)
case "inv" | "invs" | "inverse":
return inv(L)
case "pop" | "del":
return pop(L)
"pi" | "e") as constant:
case (# eval transforme la chaîne de caractère en la valeur de la variable
# en fait, eval évalue un code python
return push(eval(constant), L)
case FUNCS as fonction:
# ici, eval transforme la chaîne de caractère en fonction
return appliquer_unaire(eval(fonction), L)
case "ln":
return appliquer_unaire(log, L)
# aucune opération n'est donnée : on ne fait rien
case "":
return L
# tout autre valeur n'est pas une opération connue
case _:
print("opération inconnue !")
# on ne modifie pas L
return L