Parenthésage équilibré

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

Énoncé

Écrire equilibre s qui teste si une chaîne de '(' et ')' est correctement parenthésée, à l'aide d'une pile.

Corrigé

let equilibre s =
  let p = Stack.create () in
  let ok = ref true in
  for i = 0 to String.length s - 1 do
    if s.[i] = '(' then Stack.push '(' p
    else if s.[i] = ')' then
      if Stack.is_empty p then ok := false
      else ignore (Stack.pop p)
  done;
  !ok && Stack.is_empty p

Chaque '(' est empilé ; chaque ')' doit pouvoir dépiler une parenthèse ouvrante en attente — sinon il y a une fermante de trop (ok := false). À la fin, la pile doit être vide (sinon il reste des ouvrantes). (ignore jette la valeur dépilée, dont on n'a pas l'usage.)

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.