Introduction
Les piles sont un type de collection couramment utilisé en informatique.
Elles se définissent par leurs deux opérations clés : push et pop.
Push ajoute un élément au sommet de la pile.
Pop retire et renvoie l'élément situé au sommet.
Pense à une pile comme à une pile d'assiettes.
Tu peux soit ajouter une assiette sur le dessus de la pile, soit prendre l'assiette du haut.
Pour accéder à ce qui se trouve plus bas, il faut retirer toutes les assiettes du dessus.
L'implémentation des vecteurs de Rust, std::vec::Vec, peut servir de pile grâce à ses méthodes push() et pop().
Naturellement, push() ajoute un élément à la fin du Vec et pop() retire et renvoie le dernier élément.
Ces opérations peuvent être très rapides (O(1) en notation Big O),
ce qui en fait l'une des façons les plus idiomatiques d'utiliser un Vec.
Les piles sont utiles pour contenir un nombre arbitraire d'éléments dans un ordre donné.
Comme le dernier élément inséré est le premier élément renvoyé,
on les désigne souvent par l'acronyme LIFO (dernier entré, premier sorti).
Cet ordre inhérent peut servir à bien des choses,
notamment à suivre l'état quand on évalue une notation polonaise inversée.
Instructions
1. Vue d'ensemble
La notation polonaise inversée (NPI) est une façon d'écrire des expressions mathématiques.
Contrairement à la notation infixe traditionnelle, les opérateurs en NPI suivent leurs opérandes.
Par exemple, au lieu d'écrire :
2 + 2
on écrirait :
2 2 +
Le principal avantage de la notation polonaise inversée est qu'elle est beaucoup plus simple à analyser que la notation infixe.
La NPI élimine le besoin de gérer la priorité des opérations ou les parenthèses dans les expressions complexes.
Par exemple :
(4 + 8) / (7 - 5)
peut s'écrire
4 8 + 7 5 - /
Dans les deux cas, l'expression vaut 6.
2. Exemple
Évaluons manuellement cette expression complexe.
Comme on l'a appris dans l'introduction, l'évaluation d'une expression en NPI nécessite une pile.
Cette pile sert à stocker les valeurs numériques sur lesquelles les opérateurs agissent.
On démarre la calculatrice avec une pile vide, puis on évalue chaque élément un par un.
D'abord, on rencontre un 4,
donc on l'empile sur la pile que l'on vient de créer.
4
Ensuite, on rencontre un 8.
On l'empile également sur la pile.
4 8
Maintenant, on rencontre un +.
On dépile les deux valeurs du sommet (4 et 8),
on les additionne,
puis on empile la somme sur la pile.
12
On fait de même pour 7, 5 et - :
12 7
12 7 5
12 2
Maintenant, on rencontre un /.
Même si le dernier élément rencontré était un -,
il y a deux éléments sur la pile.
On dépile les deux éléments,
on les divise,
et on empile le résultat sur la pile.
6
Enfin, comme il y a exactement un élément sur la pile,
on peut dire que l'expression vaut 6.
3. Objectif
Ton objectif est d'écrire une calculatrice qui évalue une liste d'entrées ordonnées selon la notation polonaise inversée et qui renvoie le dernier élément de la pile.
S'il n'y a pas exactement un élément dans la pile à la fin, renvoie None.
Si un opérateur reçoit trop peu d'opérandes (comme l'entrée 2 +), renvoie None.
Pour commencer, on te fournit l'énumération et la fonction à compléter suivantes.
#[derive(Debug)]
pub enum CalculatorInput {
Add,
Subtract,
Multiply,
Divide,
Value(i32),
}
pub fn evaluate(inputs: &[CalculatorInput]) -> Option<i32> {
todo!(
"Given the inputs: {inputs:?}, evaluate them as though they were a Reverse Polish notation expression"
);
}
Exercice d'apprentissage
