Comment une calculatrice évalue-t-elle une expression avec des parenthèses ? La notation polonaise inversée

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

J'ai découvert dans le grenier une ancienne calculatrice HP sans touche « = » ni parenthèses : on tapait les nombres puis l'opération. Mon grand-père m'a expliqué que c'était la « notation polonaise inversée ». En NSI, j'ai compris qu'elle se calcule avec une pile, et j'ai voulu relier cette écriture aux priorités opératoires apprises au collège.

L'enjeu et les notions du programme

Représenter une expression par un arbre, la parcourir dans différents ordres et prouver qu'une pile l'évalue correctement.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Pour calculer $(3+4)\times (5-2)$(3+4)×(5-2), on doit respecter les parenthèses et les priorités. Un programme doit le faire mécaniquement. Problématique : comment représenter une expression pour qu'une machine l'évalue simplement ?

2. 2. Mathématiques : l'arbre d'une expression

   3,5 min

   Toute expression se représente par un arbre : la racine est la dernière opération effectuée, ici $\times$× ; ses deux sous-arbres sont $3+4$3+4 et $5-2$5-2, eux-mêmes des arbres de racines $+$+ et $-$-. Les feuilles sont les nombres.

   On lit l'arbre de trois façons. Infixe (gauche, racine, droite) : $(3+4)\times (5-2)$(3+4)×(5-2), qui demande des parenthèses. Préfixe (racine, gauche, droite) : $\times +34-52$× + 3 4 - 5 2, la notation polonaise. Suffixe (gauche, droite, racine) : $34+52-\times$3 4 + 5 2 - ×, la notation polonaise inversée.

   En notation suffixe, l'ordre des symboles suffit à indiquer l'ordre des calculs : aucune parenthèse n'est nécessaire. Le mathématicien polonais Łukasiewicz a proposé cette idée dans les années 1920.

3. 3. NSI : évaluer avec une pile

   3,5 min

   On lit l'expression suffixe de gauche à droite. Nombre : on l'empile. Opérateur : on dépile deux nombres, on calcule, on empile le résultat. Sur $34+52-\times$3 4 + 5 2 - × : pile [3], [3, 4], [7], [7, 5], [7, 5, 2], [7, 3], [21]. Le résultat est 21.

   Preuve par récurrence sur le nombre d'opérateurs : l'évaluation d'une expression suffixe correcte ajoute exactement sa valeur au sommet de la pile, sans toucher au reste. Pour une feuille, c'est vrai. Pour $AB\text{op}$A B op, $A$A empile sa valeur, puis $B$B la sienne au-dessus, et l'opérateur les combine.

   Coût : un seul parcours, chaque symbole traité en temps constant. Les compilateurs traduisent ainsi les expressions des programmes en instructions de machine à pile.

4. 4. Conclusion

   1,5 min

   Une expression est un arbre ; lue en ordre suffixe, elle se passe de parenthèses et une pile l'évalue en un seul passage. La notation polonaise inversée n'est pas une curiosité : c'est la façon dont les machines calculent. J'ouvre sur l'algorithme de la gare de triage de Dijkstra, qui convertit l'écriture usuelle en écriture suffixe.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Inverser les opérandes d'une soustraction lors du dépilement.
• Confondre notation préfixe et suffixe.
• Croire qu'il faut des parenthèses en notation suffixe.

Revoir les notions

• Calcul littéral et équations (Seconde) →
• Suites : récurrence et limites (Terminale spé maths) →

Autres questions : arbres et structures de données

• Pourquoi peut-on retrouver une donnée parmi un million en une vingtaine d'étapes seulement ?
• Pourquoi l'ordre dans lequel on range des données dans un arbre change-t-il tout ?
• Comment un hôpital ou un ordinateur peut-il toujours traiter en premier le cas le plus urgent, sans trier sans cesse ?
• Comment compresser un texte sans perdre la moindre information ?

Toutes les questions maths-nsi →