L’écriture polonaise inverse des expressions mathématiques place l’opérateur après ses opérandes. Cette notation ne nécessite ni l’utilisation des parenthèses ni la définition des règles de priorité des opérateurs.
Ainsi l’expression l’expression (1+2×3)×4 s’écrit 1 2 3 × + 4 ×.
La valeur d’une telle expression peut être calculée facilement en utilisant une pile pour stocker les résultats intermédiaires. Pour cela, on observer un à un les éléments de l’expression et on effectue les actions suivantes :
- si on voit un nombre, on le place sur la pile ;
- si on voit un opérateur binaire, on récupère les deux nombres au sommet de la pile, on leur applique l’opérateur, et on replace le résultat au sommet de la pile.
Si l’expression est bien écrite, il doit toujours y avoir deux nombres sur la pile lorsqu’un opérateur apparaît et à la fin du processus il ne doit rester qu’un seul nombre sur la pile. Ce nombre est le résultat.
L’opérateur unaire − (l’opposé) devra être considéré comme un opérateur binaire dans cette implémentation : −3 sera donc écrit 0 3 −.
Écrire une fonction prenant en paramètre une chaîne de caractères représentant une expression en notation polonaise inverse composée d’additions et de multiplications de nombres entiers et renvoyant la valeur de cette expression. On supposera que les éléments de cette expression sont séparés par des espaces.
Attention, cette fonction ne doit pas renvoyer de résultat si l’expression est mal écrite.