status: hidden
title: Python — Parenthésons
slug: eiRah1ch-parenthesons
robots: noindex


# Partie Ⅰ


Après Epitech Digital, et un doctorat en informatique vous rejoignez
une équipe chargée de concevoir le prochain langage de programmation à
la mode : le Morecambe.

Dans l’equipe « ASV », « Age^WAnalyse Syntaxique et Validation », vous
travaillez sur le parenthésage des expressions :

- `(a + b)` est valide.
- `)a + b(` n’est pas valide.
- `(a + (b + c))` est valide.
- `(a + (b + c)` n’est pas valide.
- `a * (b + c) + (d / 2)` est valide…

Jusque-là ça va, mais Morecambe est un langage moderne, il ne s’arrête
pas aux mathématiques classiques, et permet d’exprimer de la logique
combinatoire, du lambda-calcul, de la sémantique dénotationnelle (en
convergence et en divergence), et j’en passe, ainsi :

- `(λa ∘ λb)(3)` est valide, c’est une simple composition des
  fonctions `a` et `b`, immédiatement appellée.
- `⍼((a∘b)(3))|⍼((c∘d)(12))` est valide, c’est le « Right Angle with
  Downwards ZigZag Arrow » qui permet la dénotation (divergente, pour
  le coup), le `|` ne servant qu’à chaîner, comme en bash,
  naturellement.
- `[¬(a ⋀ b) ⋁ ¬(c ⋀ d)] ∀ a⍼((c∘d)(12)` n’est cependant **PAS**
  valide, bien qu’[Augustus De
  Morgan](https://fr.wikipedia.org/wiki/Lois_de_De_Morgan) aurait pu
  la corriger en un coup de cuiller à pot.

Votre première tâche sera donc d’écrire une fonction, en Python (il
faudra la réecrire en Morecambe une fois le compilateur Morecambe
fonctionnel, pour compiler Morecambe en Morecambe et boucler la
boucle, en attendant, on code en Python). Une fonction nommée
`is_correctly_balanced` qui prend en paramètre une chaîne de
caractères nommée `expression`, et qui renvoie `True` si l’expression
est correctement paremthésée, et `False` dans le cas
contraire.

L’équipe vous a préparé quelques tests unitaires et vous aurez la
bienveillance de les stocker dans le projet afin de pouvoir les
exécuter avec `pytest` :

```python
def test_bare():
    assert is_correctly_balanced("") is True
    assert is_correctly_balanced("()") is True
    assert is_correctly_balanced("(((())))") is True
    assert is_correctly_balanced("()()()()") is True
    assert is_correctly_balanced("()(())()") is True
    assert is_correctly_balanced(")(") is False
    assert is_correctly_balanced("(((") is False
    assert is_correctly_balanced("((()") is False
    assert is_correctly_balanced("()))") is False
    assert is_correctly_balanced("()()()(") is False

def test_full():
    assert is_correctly_balanced("(a + b)")
    assert not is_correctly_balanced(")a + b(")
    assert is_correctly_balanced("(a + (b + c))")
    assert not is_correctly_balanced("(a + (b + c)")
    assert is_correctly_balanced("a * (b + c) + (d / 2)")
    assert is_correctly_balanced("(λa ∘ λb)(3)")
    assert is_correctly_balanced("⍼((a∘b)(3))|⍼((c∘d)(12))")
    assert not is_correctly_balanced("[¬(a ⋀ b) ⋁ ¬(c ⋀ d)] ∀ a⍼((c∘d)(12)")
```

Dites, à quel point c’est frustrant si je vous dis que `((()))` écrit
à l’envers ça donne `)))(((` ?


# Partie Ⅱ

En rédigant votre fonction vous remarquez un fait amusant : donné un
certain nombre de paires de parenthéses, il n’y a qu’un nombre fini de
possibilités pour les agencer.

Vous ne pouvez donc vous retenir d’implementer une fonction pour toutes les
lister !

Votre fonction doit s’appeler `gen_correctly_balanced_expressions` et
prendre un seul parametre `n` : le nombre de paires de
parenthéses.

Elle doit renvoyer un iterable de tous les parenthésages possibles,
chaque parenthésage étant exprimé sous la forme d’une chaine de
caractères. Vous devinerez vite qu’il n’existe qu’une seule manière de
parenthéser une seule paire de parenthéses, puis vous découvrirez
qu’il existe

- deux manières de parenthéser deux paires,
- 5 manières d’en parenthéser trois,
- 14 d’en parenthéser 4,
- ...
- 4862 d’en parenthéser 9...


Voici par exemple les 14 parenthésages valides avec quatres paires de
parenthéses :

- `(((())))`
- `((()()))`
- `(()(()))`
- `(()()())`
- `((())())`
- `()((()))`
- `()(()())`
- `()()(())`
- `()()()()`
- `()(())()`
- `(())(())`
- `(())()()`
- `((()))()`
- `(()())()`

Vous utiliserez cette fonction pour tester votre première fonction
avec pytest, prouvant sa robustesse, et impressionant de fait votre
équipe.


# Partie Ⅲ


Il est maintenant tard, mais vous n’arrivez pas à décrocher de vos
parenthésages. Vous contemplez votre travail, vous jouez avec
`gen_correctly_balanced_expressions(5)`,
`gen_correctly_balanced_expressions(6)`… vous n’êtes plus très
productif à cette heure de la nuit, mais ces fonctions vous
distraient. Vous vous dites que ça pourraît être joli si on pouvait
remplacer les parenthéses par d’autres symboles…

Vous ajoutez donc deux arguments optionnels à votre fonction :
`opening`, et `closing`, qui respectivement valent par defaut `"("`,
et `")"` afin de ne pas changer le comportement d’origine de votre
fonction.

Et vous voilà parti à jouer avec votre nouvelle fonction :

- `gen_correctly_balanced_expressions(4, "[", "]")`
- `gen_correctly_balanced_expressions(4, "<", ">")`
- `gen_correctly_balanced_expressions(4, "la", "li")`
- `gen_correctly_balanced_expressions(4, "Tum ", "Pak ")`
- `gen_correctly_balanced_expressions(4, "𝅗𝅥", "𝅘𝅥𝅮")`
- `gen_correctly_balanced_expressions(4, "Je suis en retard…", "en retard…")`


# Partie Ⅳ

Il est vraiment tard cette fois, mais vous décidez de suivre le lapin
blanc jusqu’au fond du terrier.

Et ça y est, vous testez enfin :

`gen_correctly_balanced_expressions(5, "1", "0")`

Du binaire… des nombres ! Et aucun ne commence par zéro !! Et ils
sont tous pairs ! Ça ne peut pas être une coïncidence…

Vous rédigez alors une fonction `gen_balanced_sequence` qui prend en
paramètre `n`, le nombre de paires de bits à utiliser, et qui renvoie
un iterable de nombres entiers ordonnés par ordre croissant : les
nombres genérés par votre expérience précédente. Ces séquences sont
interessantes, mais trop courtes :

```text
2
```

puis :

```text
10
12
```

puis :

```text
42
44
50
52
56
```

…

Vous décidez alors de rédiger une fonction `gen_balanced_sequences`
(notez le pluriel) qui ne prend pas de paramètre, mais qui renvoie un
itérable infini (ou qui affiche et ne renvoie rien, à votre guise), des nombres
genérés par la fonction précédente, vous obtenez alors :

```text
2
10
12
42
44
50
52
56
170
172
…
```

Vous contemplez la séquence ainsi générée, et vous hésitez entre aller
dormir et vous lancer dans une thèse pour étudier cette séquence…