Parenthésage équilibré

Piles, files et tables de hachage · niveau 2

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

Énoncé

Corrigé

Exercices semblables