====== Calculatrice en notation polonaise inversée ======

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)%%''...

===== Notation polonaise inversée =====

L'idée vient du mathématicien polonais [[https://fr.wikipedia.org/wiki/Jan_%C5%81ukasiewicz|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**.

===== Utilisation d'une pile =====

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.

<WRAP info>
{{ :nsi:tds:hp48g.jpg?direct&35|}}
Vers 1990, Hewlett Packard commercialisait des calculatrices, comme la 48G ci-contre, utilisant la notation polonaise inversée. Les expressions étaient entrées dans une pile et au lieu d'entrer par exemple ''45 * 3'', on entrait ''45 3 *''. C'est déroutant au début mais une fois l'habitude prise, c'est beaucoup plus efficace !
</WRAP>

===== À faire =====

É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.