# AP2 — Des parenthèses bien placées

Atelier facultatif après AP2 : le parcours principal porte sur un
interpréteur à arbre avec variables et conditionnelles. Cet exercice fournit un entraînement supplémentaire sur les préfixes.


## Un compteur suffit-il ? (40 min)

Nous voulons vérifier une chaîne contenant uniquement `(` et `)`.
Elle est valide si chaque fermeture correspond à une ouverture antérieure
et si toutes les ouvertures sont refermées à la fin. La chaîne vide est
valide. Tout autre symbole, y compris un espace, doit être signalé.

Ce notebook est autonome : aucune cellule d'un autre fichier n'est requise.
Sauvegardez-le dans `entrainement/`. Le seul fichier collecté pour AP2 est
la série des cinq notebooks numérotés dans `AP2/`, auxquels vous reviendrez après cet atelier.

Évaluez les cellules dans l'ordre. Remplacez les `nil` des cellules à
compléter, puis lancez la vérification juste en dessous. Un message d'erreur
vous indique un cas à reprendre ; corrigez votre code et réévaluez les deux
cellules. Dans les vérifications, `for {texte, attendu} <- liste do … end`
parcourt chaque couple de la liste, et `if … do raise … end` arrête la cellule
avec un message si un cas échoue. Ce sont des outils fournis, que vous n'avez
pas à réécrire.

## Prédire avant de coder (10 min)

Pour chacun des textes suivants, indiquez s'il est valide : `"()"`,
`"(())"`, `"()()"`, `")("`, `"(()"`, `"(x)"` et `""`.
Expliquez pourquoi compter seulement le total des ouvertures et des
fermetures ne permet pas de trancher pour `")("`.

Nous allons parcourir le texte de gauche à droite. Un accumulateur
`ouvertes` compte les parenthèses ouvertes qui attendent encore leur
fermeture. Sur `(` il augmente, sur `)` il diminue. Une fermeture avec
`ouvertes == 0` est immédiatement incorrecte.

Complétez les valeurs manquantes de cette trace sur papier :

| Texte restant | Ouvertures en attente |
|---|---:|
| `"(())"` | 0 |
| `"())"` | … |
| `"))"` | … |
| `")"` | … |
| `""` | … |

## Écrire les clauses (20 min)

La fonction d'entrée `Parentheses.verifie/1` démarre le parcours à 0 ;
elle vous est fournie. Complétez les clauses de `parcourir/2` :

- à la fin, le succès est `{:ok, 0, ""}` si le compteur vaut 0 ;
- à la fin avec des ouvertures en attente, l'erreur est
  `{:error, :ouverture_non_fermee, ""}` ;
- sur `)` avec un compteur nul, l'erreur est
  `{:error, :fermeture_inattendue, texte_non_consomme}` ;
- sur un symbole inconnu, l'erreur est
  `{:error, :symbole_inconnu, texte_non_consomme}`.

L'opérateur `<>` concatène deux chaînes. Dans un motif, `")" <> reste`
reconnaît le préfixe `)` et nomme la suite ; dans une expression, `")" <> reste`
recolle cette fermeture devant le reste. Utilisez cette seconde forme pour
reconstruire le reste fautif : la fermeture doit rester dans le résultat d'erreur.
Les appels récursifs, eux, ne reçoivent que `reste`.

```elixir
defmodule Parentheses do
  def verifie(texte) do
    parcourir(texte, 0)
  end

  def parcourir("", 0) do
    nil
  end

  def parcourir("", _ouvertes) do
    nil
  end

  def parcourir(")" <> reste, 0) do
    nil
  end

  def parcourir("(" <> reste, ouvertes) do
    nil
  end

  def parcourir(")" <> reste, ouvertes) do
    nil
  end

  def parcourir(texte, _ouvertes) do
    nil
  end
end
```

Vérification fournie :

```elixir
for {texte, attendu} <- [
  {"", {:ok, 0, ""}},
  {"()", {:ok, 0, ""}},
  {"(())", {:ok, 0, ""}},
  {"()()", {:ok, 0, ""}},
  {"(()())", {:ok, 0, ""}},
  {")(", {:error, :fermeture_inattendue, ")("}},
  {"())(", {:error, :fermeture_inattendue, ")("}},
  {"(()", {:error, :ouverture_non_fermee, ""}},
  {"(x)", {:error, :symbole_inconnu, "x)"}},
  {"() ", {:error, :symbole_inconnu, " "}},
  {"(é)", {:error, :symbole_inconnu, "é)"}}
] do
  if Parentheses.verifie(texte) != attendu do
    raise "Vérifiez le résultat et le reste pour #{inspect(texte)}."
  end
end
IO.puts("Parenthèses : équilibres, ordre et erreurs vérifiés")
```

## Expliquer le résultat (10 min)

Complétez cette cellule de texte :

1. Pourquoi la clause `parcourir(")" <> reste, 0)` doit-elle être placée
   avant celle dont le deuxième paramètre s'appelle `ouvertes` ?
2. En partant de `verifie/1`, le compteur peut-il devenir négatif ?
3. Sur `"())("`, quelle partie avons-nous reconnue avant l'erreur ?
   Pourquoi ne faut-il pas poursuivre jusqu'au dernier caractère ?
4. Ajoutez un cas valide et un cas invalide, puis vérifiez vos prédictions.

L'idée est adaptée de [Matching Brackets, Exercism](https://github.com/exercism/elixir/tree/main/exercises/practice/matching-brackets).
Notre alphabet est volontairement limité aux parenthèses et nous signalons
les autres symboles, tandis que l'exercice d'origine les ignore. Nous
reviendrons aux différents types de délimiteurs avec une pile : un simple
compteur ne permettra plus de vérifier leur ordre.

Sauvegardez ce notebook dans `entrainement/`. Les notebooks et les cellules à rendre seront précisés en cours, selon notre avancement. Ce complément peut être joint dans `AP2/` pour un bonus.
Si un bout de syntaxe Elixir vous manque, les
[fiches de référence](https://ap-2026.noce.fr/reference/) se consultent au besoin.

Pour toute question, vous pouvez me contacter par email :
[aurelien.noce@minesparis.psl.eu](mailto:aurelien.noce@minesparis.psl.eu).