24-NSIJ2JA1-2

  Énoncé   Sujet

1. L'expression est mal parenthésée : [2 * (i + 1) - 3) for i in range(3, 10)]

2. # évite de se répéter pour la question 3
   def compte_caracteres(txt, caracteres):
       compteur = 0
       for caractere in txt:
           if caractere in caracteres:
               compteur += 1
       return compteur
   
   def compte_ouvrante(txt):
       return compte_caracteres(txt, '({[')
   

3. def compte_fermante(txt):
       return compte_caracteres(txt, ')}]')
   

4. def bon_compte(txt):
       return compte_ouvrante(txt) == compte_fermante(txt)
   

5. Par exemple, bon_compte('](') renvoie True alors que l'expression '](' n'est pas bien parenthésée.

6. class Pile:
       def __init__(self):
           self.contenu = []
   
       def est_vide(self):
           return len(self.contenu) == 0
   
       def empiler(self, elt):
           self.contenu.append(elt)
   
       def depiler(self):
           if self.est_vide():
               return "La pile est vide."
           return self.contenu.pop()
   

7. Pour un caractère de la chaîne, l'algorithme effectue \(O(1)\) comparaisons. Ainsi, pour une chaîne de \(n\) caractères, il effectue \(\boxed{O(n)}\) comparaisons. Le nombre précis de comparaisons dépend totalement de l'implémentation.

8. def est_bien_parenthesee(chaine):
       COUPLE = {'(': ')', '[': ']', '{': '}'}
       pile = Pile()
       for c in chaine:
           if c in '([{':
               pile.empiler(c)
           elif c in ')]}':
               if pile.est_vide() or c != COUPLE[pile.depiler()]:
                   return False
       return pile.est_vide()