Considérons une expression comme "7 * 6 + 4 * (15 + 2)". On souhaite évaluer automatiquement une telle expression. La difficulté est que l'on ne peut pas évaluer au fur et à mesure de la lecture de l'expression.

En effet, il faut attendre d'avoir lu le 6 avant d'exécuter le premier *. Plus compliqué, avant de d'exécuter le premier +, il faut attendre d'avoir fini le calcul 4 * ( 15 + 2)…

L'idée vient du mathématicien polonais Jan Łukasiewicz d'où le qualificatif de “polonaise”.

Dans notre calcul, plutôt que 7 * 6, on adopte la notation 7 6 *. On lit 7 puis 6, qui sont mis de côtés. Puis la lecture de * exécute immédiatement le calcul sur les derniers nombres mis de côté.

Avant d'aller plus loin, précisons le vocabulaire : +, -, * font les opérations, ce sont des opérateurs. Les nombres subissent les opérations, ce sont des opérandes.

Dans 4 * (15 + 2), la bonne notation sera 4 15 2 + *. Et voici l'exécution correspondante :

• Lecture de 4. Mis en mémoire dans une pile → 4.
• Lecture de 15. Idem → 4:15.
• Lecture de 2. Idem → 4:15:2.
• Lecture de +. Dépilement des deux dernières opérandes et exécution : 15 + 2 = 17, puis empilement du résultat → 4:17
• Lecture de *. Dépilement de 7 et 17, exécution 4 * 17 = 68, empilement → 68
• Plus de calcul, le résultat est tout ce qui reste à dépiler : 68.

L'expression 7 * 6 + 4 * (15 + 2) peut alors être convertie en 7 6 * 4 15 2 + * +. C'est la notation polonaise inversée. Vous remarquerez que les parenthèses deviennent inutile.

Écrire le programme Python qui, partant du calcul écrit en notation polonaise inversée, avec seulement les opérateurs + - et * et des opérandes entières, exécute le calcul.