Loading [MathJax]/extensions/Safe.js

Piles et Files : parenthésage

Pour cet exercice, on utilisera les objets deque du module collections de python qui permet d'implémenter des structures de pile et de file avec des temps d'ajout / de retrait optimisés.

On rappelle que les objets deque disposent - pour faire simple - de quatre méthodes :

- pop()             pour extraire l'élément le plus à droite,
- popleft()         pour extraire l'élément le plus à gauche,
- append(elt)       pour ajouter un élément à droite,
- appendleft(elt)   pour ajouter un élément à gauche.

Et qu'enfin on peut leur appliquer la méthode len pour savoir combien ils comportent d'éléments.


On considère une chaîne de caractères comportant deux formes de parenthèses :

  • des parenthèses rondes ( et ) ,
  • des parenthèses carrées [ et ].

On dit que la chaîne est bien parenthésée :

  • si chaque ouvrante est associée à une unique fermante de même forme et réciproquement,

  • si pour chaque parenthèse ouvrante ouverte à l'intérieur d'un autre couple de parenthèses, sa parenthèse fermante se trouve également à l'intérieur du même couple.

Voici quelques exemples :

Bien parenthésée Mal parenthésée
abc (
(abc) abc)
ab[cd]ef ab)c
a[b]c(d)e a(b]c
a((b)c)d a(b(c)d
a(b[c()e]f)g a(b[c)d]e

Un algorithme classique pour tester si une chaîne de caractères est bien parenthésée est le suivant qui utilise une pile :

Parcourir la chaîne de caractères de gauche à droite :
    - Si le caractère lu est une parenthèse ouvrante l'empiler,
    - Si le caractère lu est une parenthèse fermante :
        - si la pile est vide : erreur de parenthésage,
        - si le sommet de la pile n'est pas une ouvrante de même forme : erreur de parenthésage,
        - si le sommet de la pile est une ouvrante de même forme : le dépiler,
        
À la fin du parcours :
    - si la pile n'est pas vide : erreur de parenthésage,
    - sinon : parenthésage correct.

Question 1 :

Pourquoi dans l'algorithme est-il important de traiter le cas où la pile est vide AVANT le cas où le sommet de la pile n'est pas une ouvrante de même forme ?

Solution

Parce que pour parler de sommet de la pile, il faut s'assurer que celle-ci n'est pas vide.

Or si elle est vide, son cas a été traité avant (et met fin à l'algorithme puisqu'on sait alors que le parenthésage est incorrcet).

Question 2 :

Dans un algorithme, il y a l'instruction suivante à implémenter :

  • si le sommet de la pile est différent de zéro : le dépiler et renvoyer False,
  • si le sommet de la pile est égal à zéro : le dépiler,

Est-ce que cela correspond à la séquence d'instructions ci-dessous (où p est la pile) ?

if p.pop() != 0:
    return False
else:
    p.pop()
Solution

Non, car dans cette séquence d'instructions, si le sommet de la pile est égal à zéro, on effectue un pop() supplémentaire. Donc finalement on a retiré deux fois le sommet de la pile, ce qui revient à en retirer les deux éléments du sommet.

Il aurait fallu cette séquence d'instructions :

if p.pop() != 0:
    return False
else:
    pass #on ne fait rien

Question 3 :

Compléter le code de la fonction verifier_parenthesage ci-dessous afin qu'elle mette en œuvre l'algorithme de vérification de parenthésage. Elle renverra True si le parentéhsage est correct et False sinon.

Entrée[ ]:
Entrée[ ]:
Solution 
from collections import deque
    
def verifier_parenthesage(chaine):
    pile = deque()
    
    for car in chaine:
        if car == '(' or car == '[':
            pile.append(car)
    
        elif car == ')':
            if len(pile) == 0 :
                return False
            if  pile.pop() != '(':
                return False

        elif car == ']':
            if len(pile) == 0:
                return False
            if pile.pop() != '[':
                return False

    if len(pile) != 0 :
        return False
    else:
        return True

Question 4 :

Remplacer les quatre dernières lignes de code de la fonction par une unique ligne de code.

Entrée[ ]:
Solution 
    return len(pile) == 0

Question 5 :

À partir de l'indice d'une parenthèse ouvrante dans une chaîne de caractères bien parenthésée, on cherche à trouver l'indice de la parenthèse fermante correspondante.

L'idée est de parcourir la chaîne de caractères à partir de l'indice de la parenthèse ouvrante puis d'empiler / dépiler comme précédemment les parenthèses et crochets ouvrants et fermants en gardant une trace de l'indice où l'on est dans la chaîne de caractères.

Puisque l'énoncé nous indique que la chaîne est bien parenthésée, lorsqu'on tombe sur une parenthèse fermante, on peut dépiler la pile sans effectuer de test conditionnel.

On arrête le parcours dès que la pile redevient vide, on obtient alors l'indice de la fermante correspondant à l'ouvrante initiale.

Compléter le code ci-dessous qui implémente cette recherche de parenthèse fermante :

Entrée[ ]:
Entrée[ ]:
Solution 
from collections import deque
    
def trouver_fermante(chaine, indice_initial):
    assert verifier_parenthesage(chaine), "La chaine doit etre bien parenthésée !"
    
    pile = deque()
    pile.append(chaine[indice_initial])
    
    indice = indice_initial + 1
    while len(pile) != 0 :
        car = chaine[indice]
        if car == '(' or car == '[':
            pile.append(car)
        elif car == ')' or car == ']':
            pile.pop()
        indice = indice + 1
        
    return indice - 1
Chargement de Basthon...