Prépa Code Connexion Inscription

Écrire une fonction evaluer : string list -> int qui évalue une expression arithmétique en notation polonaise inverse (postfixe).

L'expression est donnée comme une liste de jetons (chaînes de caractères). Chaque jeton est : - soit un entier (lisible par int_of_string), - soit un opérateur parmi "+", "-", "*".

L'algorithme classique utilise une pile : - si le jeton est un entier, on l'empile, - si c'est un opérateur, on dépile les deux derniers opérandes b puis a, et on empile a op b.

À la fin, le résultat est l'unique élément restant sur la pile.

On suppose que l'expression est bien formée.

On pourra utiliser le module Stack.