Épreuve pratique NSI 2024 — Sujet 08 : codage par différence, arbre d'une expression

Épreuve pratique de NSI, session 2024 — sujet n°08 de la banque nationale. Durée : 1 heure, sur ordinateur. Le candidat traite les deux exercices, notés chacun sur 10 points.

Exercice 1 — codage par différence (delta encoding)

Le codage par différence (delta encoding en anglais) permet de compresser un tableau de données en indiquant, pour chaque donnée, sa différence avec la précédente (plutôt que la donnée elle-même). On se retrouve alors avec un tableau de données plus petites, nécessitant moins de place en mémoire. Cette méthode se révèle efficace lorsque les valeurs consécutives sont proches.

Programmer la fonction delta(liste) qui prend en paramètre un tableau non vide de nombres entiers et qui renvoie un tableau contenant les valeurs entières compressées à l'aide de cette technique.

Exemples :

>>> delta([1000, 800, 802, 1000, 1003])
[1000, -200, 2, 198, 3]
>>> delta([42])
[42]

Exercice 2 — parcours infixe d'un arbre d'expression

Une expression arithmétique ne comportant que les quatre opérations $+$, $-$, $\times$, $\div$ peut être représentée sous forme d'arbre binaire. Les nœuds internes sont des opérateurs et les feuilles sont des nombres. Dans un tel arbre, la disposition des nœuds joue le rôle des parenthèses que nous connaissons bien.

En parcourant en profondeur infixe l'arbre binaire ci-dessus, on retrouve l'expression notée habituellement :

La classe Expr ci-après permet d'implémenter une structure d'arbre binaire pour représenter de telles expressions. Compléter la méthode récursive infixe qui renvoie une chaîne de caractères contenant des parenthèses représentant l'expression arithmétique sur laquelle on l'applique.

class Expr:
    """Classe implémentant un arbre d'expression."""
 
    def __init__(self, g, v, d):
        """un objet Expr possède 3 attributs :
        - gauche : la sous-expression gauche ;
        - valeur : la valeur de l'étiquette, opérande ou nombre ;
        - droite : la sous-expression droite."""
        self.gauche = g
        self.valeur = v
        self.droite = d
 
    def est_une_feuille(self):
        """renvoie True si et seulement
        si le noeud est une feuille"""
        return self.gauche is None and self.droite is None
 
    def infixe(self):
        """renvoie la représentation infixe de l'expression en
        chaine de caractères"""
        s = ...
        if self.gauche is not None:
            s = '(' + s + ... .infixe()
        s = s + ...
        if ... is not None:
            s = s + ... + ...
        return s

Exemples :

>>> a = Expr(Expr(None, 1, None), '+', Expr(None, 2, None))
>>> a.infixe()
'(1+2)'
>>> b = Expr(Expr(Expr(None, 1, None), '+', Expr(None, 2, None)),
    '*', Expr(Expr(None, 3, None), '+', Expr(None, 4, None)))
>>> b.infixe()
'((1+2)*(3+4))'
>>> e = Expr(
    Expr(Expr(None, 3, None), '*', Expr(Expr(None, 8, None),
         '+', Expr(None, 7, None))),
    '-', Expr(Expr(None, 2, None), '+', Expr(None, 1, None)))
>>> e.infixe()
'((3*(8+7))-(2+1))'