Utiliser une pile pour évaluer une notation en polonais inverse
- Fiche de cours
- Quiz et exercices
- Vidéos et podcasts
Utiliser un type de données abstrait pour évaluer des expressions en polonais inverse.
- Pour écrire des expressions algébriques, on peut utiliser différentes notations : infixée (ou infixe), préfixée (ou préfixe) ou postfixée (ou postfixe).
- La notation en polonais inverse est un type de notation qui est qualifié de postfixé. Cette notation permet d’écrire de façon non ambiguë les calculs, sans parenthèses et en utilisant des piles.
- Pour obtenir l’évaluation d’une expression en polonais inverse, c’est-à-dire obtenir la valeur décimale de cette expression, on peut utiliser la structure de données de type pile.
- Programmation orientée objet avec la notion de classe
- Pile et file
Pour écrire des expressions algébriques, on peut utiliser différentes notations : infixée (ou infixe), préfixée (ou préfixe) ou postfixée (ou postfixe).
Les notations infixée, préfixée et postfixée d’une expression algébrique se distinguent par la position que prennent les opérateurs et les opérandes.
Les opérateurs sont +, –, *, /, ** ou ^ (pour la puissance).
4 + 5 * 3 est une expression algébrique.
Les opérateurs sont + et *. Les opérandes sont 4, 5 et 3.
La notation infixée est celle qu’on utilise en mathématiques. On l’utilise lorsqu’on réalise des calculs.
- 3 + 4
- ((1 + 2) × 3)4
Dans la notation préfixée, on écrit l’opérateur puis les opérandes.
- + 3 4
- + 1 2 × 3 ^ 4
Dans la notation postfixée, on écrit les opérandes puis les opérateurs.
- 3 4 +
- 1 2 + 3 × 4 ^
La notation en polonais inverse est apparue dans les années 1940, puis fut utilisée dans les calculatrices grand public de l’entreprise HP (Hewlett-Packard) dans les années 1960.
Une pile est un type abstrait de structure de données, dans lequel on empile et dépile les données : les dernières données ajoutées à une pile sont les premières à sortir.
La notation infixée « a operateur b » se note « a b operateur » dans la notation en polonais inverse, avec a et b deux opérandes.
- La notation infixée « 3 + 4 » se note « 3 4 + » en NPI.
- La notation infixée « ((1 + 2) × 3)4 » se note « 1 2 + 3 × 4 ^ » en NPI.
- Le but n’est pas ici d’effectuer la conversion de la notation infixée vers la notation postfixée.
- L’algorithme qui permet cette conversion se nomme l’algorithme de Shunting-yard ou algorithme de la gare de triage.
À l’aide d’un algorithme, on souhaite évaluer une expression postfixée, qui a été conçue avec une notation postfixée telle que le polonais inverse (NPS).
Pour évaluer une expression postfixée, c’est-à-dire obtenir la valeur décimale de cette expression, l’algorithme commence par lire un par un les caractères de l’expression postfixée.
- Si le caractère lu est un opérande (nombre), alors on l’empile en haut de la pile.
- Si le caractère lu est un opérateur (symbole
mathématique), alors :
- on dépile les deux opérandes qui se trouvent en haut de la pile ;
- on calcule le résultat en appliquant l’opérateur sur les deux opérandes dépilés ;
- et on empile le résultat en haut de la pile.
On empile les opérandes et non les opérateurs.
Une fois tous les caractères lus, la pile ne contient qu’un seul élément qui correspond au résultat final.
On souhaite évaluer l’expression postfixée 1 2 + 4 * 5 +, c’est-à-dire obtenir sa valeur décimale.
On lit un à un les caractères de l’expression postfixée 1 2 + 4 * 5 + pour l’évaluer.
- Les opérateurs sont les éléments + et *.
- Les opérandes sont les éléments 1, 2, 4 et 5.
- Le premier opérateur « + » permet de dépiler les deux opérandes 1 et 2, et d’empiler le résultat de l’opération 1 + 2.
Une expression postfixée est représentée par un tableau qui ne contient que des caractères : on obtient une liste.
« 3 4 + » est noté ['3','4','+'].
Cette méthode renvoie True si tous les éléments de la chaine de caractères sont des chiffres et False sinon.
Soit a='41'. La méthode a.isdigit() renvoie True car cette chaine de caractères ne possède que des chiffres (opérandes).
Pour implémenter (définir) l’évaluation d’une expression postfixée en Python, on empile les opérandes, on va donc naturellement utiliser la classe Pile.
Voici l’implémentation de la classe Pile.
Les différentes étapes sont indiquées dans les commentaires verts.
Cette fonction renvoie un nombre flottant (nombre décimal).
Voici l’implémentation de cette fonction.
Voici l’explication de ce code ligne par ligne.
| Python | Explication |
| def evalpostfixe(liste): |
On définit la fonction evalpostfixe qui prend pour
paramètre une liste liste. Cette fonction permet d’évaluer la liste. |
|
“““Evaluation d’une expression postfixe Entrée : une liste représentant une expression postfixée Sortie : un flottant””” |
On documente la fonction. |
| p=Pile() | On affecte une pile vide à la variable p. |
| for el in liste: | On parcourt les éléments de la liste. |
|
if el.isdigit(): p.empiler(float(el)) |
Si l'élément de la liste est un nombre, alors on l’empile en tant que nombre. |
|
if el=='+': a=p.depiler() b=p.depiler() p.empiler(b+a) |
Si c’est l’opérateur
« + »
(addition), alors :
|
|
if el=='–': a=p.depiler() b=p.depiler() p.empiler(b–a) |
Si c’est l’opérateur
« – »
(soustraction), alors :
|
|
if el=='*': a=p.depiler() b=p.depiler() p.empiler(b*a) |
Si c’est l’opérateur
« * »
(multiplication), alors :
|
|
if el=='/': a=p.depiler() b=p.depiler() assert a!=0, “Diviser par zéro” p.empiler(b/a) |
Si c’est l’opérateur
« / »
(division), alors :
|
|
if el=='^': a=p.depiler() b=p.depiler() p.empiler(b**a) |
Si c’est l’opérateur
« ^ »
(puissance), alors :
|
| return p.depiler() | On affiche le résultat final en dépilant entièrement la pile p. |
On souhaite évaluer l’expression 4 5 * 3 +.
Voici l’exécution de la fonction sur Python Tutor avec la liste ['4','5','*','3','+'].
On obtient 23.0, ce qui signifie que l’écriture décimale du résultat est 23.
Évalue ce cours !
Des quiz et exercices pour mieux assimiler sa leçon
La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.
Des exercices variés pour ne pas s’ennuyer
Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !
Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.
Des quiz pour une évaluation en direct
Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.
myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.
Des vidéos et des podcasts pour apprendre différemment
Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.
Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !
Des podcasts pour les révisions
La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.
Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.
Des vidéos de cours pour comprendre en image
Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !
Fiches de cours les plus recherchées
NSI
Choisir une structure de données en fonction de la situation
NSI
Rechercher une valeur dans une liste et dans un dictionnaire
NSI
Comprendre la structure hiérarchique des arbres binaires
NSI
Étudier et implémenter un arbre binaire
NSI
Utiliser des arbres binaires de recherche
NSI
Comprendre la structure des graphes
NSI
Implémenter un graphe
NSI
Passer d'une représentation d'un graphe à une autre
NSI
Comprendre le modèle relationnel d'une base de données
NSI
Utiliser l'algèbre relationnel dans une base de données relationnelle
Fermer
Accédez gratuitement à
