Adloun

Évaluer une expression postfixe

Exercice · OCaml (option informatique), chapitre 8 — Piles, files et tables de hachage

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

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

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.