Évaluer une expression postfixe

Piles, files et tables de hachage · niveau 3 (difficile)

Énoncé

On représente une expression en notation postfixe (polonaise inverse) par une liste de jetons :

type jeton = Nombre of int | Add | Mul

Écrire evalue qui évalue une telle liste à l'aide d'une pile. Exemple : [Nombre 2; Nombre 3; Nombre 4; Mul; Add] vaut $2 + 3 \times 4 = 14$ .

Corrigé

let evalue jetons =
  let p = Stack.create () in
  let traite j =
    match j with
    | Nombre n -> Stack.push n p
    | Add -> let b = Stack.pop p in let a = Stack.pop p in Stack.push (a + b) p
    | Mul -> let b = Stack.pop p in let a = Stack.pop p in Stack.push (a * b) p
  in
  List.iter traite jetons;
  Stack.pop p

On empile chaque nombre ; à chaque opérateur, on dépile les deux derniers opérandes, on calcule, et on rempile le résultat. À la fin, la pile contient l'unique résultat. C'est le principe d'une calculatrice à pile — et un classique d'usage conjoint des piles (chapitre 8), des types sommes (chapitre 3) et des listes (chapitre 2).

Énoncé

Corrigé

Exercices semblables