Chapitre 3 : Structures de données.

1. Exercice:

class Truc:
    def __init__(self):
        self.__liste=[]

    def ajout(self,objet):
        self.__liste.insert(0,objet)

    def enleve(self):
        return self.__liste.pop()

    def nombre_objets(self):
        return len(self.__liste)

En considérant la classe Truc ci-dessus :

1. Comment qualifier l'attribut .__liste?

2. nouvel_objet=Truc()
   nouvel_objet.ajout(3)
   nouvel_objet.ajout(2)
   nouvel_objet.ajout(10)
   print(nouvel_objet.enleve())
   print(nouvel_objet.nombre_objets())

   Qu'affiche le code suivant?

3. Schématisez sur votre cahier la façon dont se comporte un objet de classe Truc.

   Comment appelle-t-on cela dans la vie courante?

10. Exercice:

Le but est ici de créer une class TableauStatique qui permet de créer un objet qui est de type statique, indexé et linéaire.

On souhaite avoir les caractèristiques suivantes:

• La taille du tableau est fixé à la création à l'aide de def __init__(self,taille).
• A l'initialisation, le tableau est rempli avec des None. Cela doit être un attribut privé.
• On possède l'attribut taille qui permet de connaitre la taille du tableau.
• Un tableau est considéré comme vide s'il n'est rempli que de None : on aura ainsi la méthode vide(self) qui renvoie un booléen. La méthode renvoie True si le tableau est composé que de None et False sinon.
• On possède la méthode change(self,i,data) qui permet de changer l'élément d'indice i par le contenu de data.
• On possède la méthode effacer(self,i) qui permet de remplacer l'élément d'indice i par None.
• On possède la méthode connaitre(self,i) qui permet de savoir le contenu de l'élément i.
• On possède la méthode affiche_tout(self) qui permet de voir tout le contenu du tableau.

11. Exercice:

Creer une fonction tableau_alea(n) qui prend en paramètre un int nommé n et qui retourne un objet TableauStatiquede taille n contenant des nombres entiers générés aléatoirement entre -20 et 20.

14. Exercice:

1. Recopier la class Pile dans un fichier python.
2. Créer une fonction caracteres_dans_pile qui prend comme paramètre un string et renvoie une pile contenant les caractères de ce string.
3. Créer une fonction nb_espaces qui prend comme paramètre une pile contenant des caractères et renvoyant le nombre de fois où le caractère espace apparait sous la forme d'un integer.

15. Exercice:

Créer la classe File contenant les méthodes suivantes:

• enfiler(self,data) qui insère un objet dans la file
• defiler(self) qui extrait le dernier de la file
• vide(self) qui teste si la file est vide
• non_vide(self) qui teste si la file est non vide

16. Exercice:

En utilisant la classe File :

1. Creer une fonction extraire(un_texte) qui prend un string et met chaque caractère dans une file.
2. Creer une fonction voyelle(une_file) qui prend une file qui contient des caractères et qui affiche (print) les voyelles présentes.
3. Creer une fonction plus_grande(une_file) qui prend une file composée uniquement d'integers et renvoie le plus grand nombre de la file .

17. Exercice : (sujet 8 -2023)

Nous avons l’habitude de noter les expressions arithmétiques avec des parenthèses comme par exemple : \((2 + 3) \times 5\).

Il existe une autre notation utilisée par certaines calculatrices, appelée notation postfixe, qui n’utilise pas de parenthèses. L’expression arithmétique précédente est alors obtenue en saisissant successivement 2, puis 3, puis l’opérateur +, puis 5, et enfin l’opérateur \( \times \). On modélise cette saisie par le tableau [2, 3, '+', 5, '*'].

Autre exemple, la notation postfixe de \( 3 \times 2 + 5\) est modélisée par le tableau :

[3, 2, '*', 5, '+']

D’une manière plus générale, la valeur associée à une expression arithmétique en notation postfixe est déterminée à l’aide d’une pile en parcourant l’expression arithmétique de gauche à droite de la façon suivante :

• si l’élément parcouru est un nombre, on le place au sommet de la pile
• si l’élément parcouru est un opérateur, on récupère les deux éléments situés au sommet de la pile et on leur applique l’opérateur. On place alors le résultat au sommet de la pile
• à la fin du parcours, il reste alors un seul élément dans la pile qui est le résultat de l’expression arithmétique.

Dans le cadre de cet exercice, on se limitera aux opérations \( \times \) et \(+\) .

Pour cet exercice, on dispose d’une classe Pile qui implémente les méthodes de base sur la structure de pile.

Compléter le script de la fonction eval_expression qui reçoit en paramètre une liste python représentant la notation postfixe d’une expression arithmétique et qui renvoie sa valeur associée.

class Pile:
    """
    Classe definissant une structure de pile.
    """
    def __init__(self):
        self.contenu = []

    def est_vide(self):
        """
        Renvoie le booleen True si la pile est vide, False sinon.
        """
        return self.contenu == []

    def empiler(self, v):
        """
        Place l'element v au sommet de la pile
        """
        self.contenu.append(v)

    def depiler(self):
        """
        Retire et renvoie l'element place au sommet de la pile,
        si la pile n'est pas vide.
        """
        if not self.est_vide():
            return self.contenu.pop()


def eval_expression(tab):
    p = Pile()
    for ... in tab:
        if element != '+' ... element != '*':
            p.empiler(...)
        else:
            if element == ...:
                resultat = p.depiler() + ...
            else:
                resultat = ...
            p.empiler(...)
    return ...

Exemples :

>>> eval_expression([2, 3, '+', 5, '*'])
25

18. Exercice : (sujet 10 - 2023)

On dispose de chaînes de caractères contenant uniquement des parenthèses ouvrantes et fermantes.

Un parenthésage est correct si :

• le nombre de parenthèses ouvrantes de la chaîne est égal au nombre de parenthèses fermantes.
• en parcourant la chaîne de gauche à droite, le nombre de parenthèses déjà ouvertes doit être, à tout moment, supérieur ou égal au nombre de parenthèses déjà fermées.

Ainsi, "((()())(()))" est un parenthésage correct.

Les parenthésages "())(()" et "(())(()" sont, eux, incorrects.

On dispose de la classe Pile décrite plus bas.

On souhaite programmer une fonction parenthesage qui prend en paramètre une chaîne de caractères ch formée de parenthèses et renvoie True si la chaîne ch est bien parenthésée et False sinon.

Cette fonction utilise une pile et suit le principe suivant : en parcourant la chaîne de gauche à droite, si on trouve une parenthèse ouvrante, on l’empile au sommet de la pile et si on trouve une parenthèse fermante, on dépile (si possible) la parenthèse ouvrante stockée au sommet de la pile.

La chaîne est alors bien parenthésée si, à la fin du parcours, la pile est vide.

Elle est, par contre, mal parenthésée :

• si dans le parcours, on trouve une parenthèse fermante, alors que la pile est vide;
• ou si,à la fin du parcours, la pile n'est pas vide.

Compléter le code ci-dessous :

class Pile:
    """
    Classe definissant une pile
    """
    def __init__(self):
        self.valeurs = []

    def est_vide(self):
        """
        Renvoie True si la pile est vide, False sinon
        """
        return self.valeurs == []

    def empiler(self, c):
        """
        Place l'element c au sommet de la pile
        """
        self.valeurs.append(c)

    def depiler(self):
        """
        Supprime l'element place au sommet de la pile, a condition qu'elle soit non vide
        """
        if self.est_vide() == False:
            self.valeurs.pop()


def parenthesage(ch):
    """
    Renvoie True si la chaine ch est bien parenthesee et False sinon
    """
    p = Pile()
    for c in ch:
        if c == ...:
            p.empiler(c)
        elif c == ...:
            if p.est_vide():
                return ...
            else:
                ...
    return p.est_vide()

Exemples :

>>> parenthesage("((()())(()))")
True
>>> parenthesage("())(()")
False
>>> parenthesage("(())(()")
False