Solution de Évaluation d'une expression postfixée - Sujet 35 - EP NSI 2025

Exercice 1

Sur le réseau social TipTop, on s’intéresse au nombre de « like » des abonnés. Les données sont stockées dans des dictionnaires où les clés sont les pseudos et les valeurs correspondantes sont les nombres de « like » comme ci-dessous :

{ 'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50 }

Écrire une fonction max_dico qui :

• prend en paramètre un dictionnaire dico non vide dont les clés sont des chaînes de caractères et les valeurs associées sont des entiers ;
• et qui renvoie un tuple dont :
  • la première valeur est la clé du dictionnaire associée à la valeur maximale ;
  • la seconde valeur est la première valeur maximale présente dans le dictionnaire.

Exemples :

>>> max_dico({ 'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50 })
('Ada', 201)
>>> max_dico({ 'Alan': 222, 'Ada': 201, 'Eve': 222, 'Tim': 50 })
('Alan', 222)

Exercice 2

Nous avons l’habitude de noter les expressions arithmétiques avec des parenthèses comme par exemple : (2 + 3) × 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 ×. On modélise cette saisie par le tableau [2, 3, '+', 5, '*'].

Autre exemple, la notation postfixe de 3 × 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 × 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 définissant une structure de pile."""
    def __init__(self):
        self.contenu = []

    def est_vide(self):
        """Renvoie un booléen indiquant si la pile est vide."""
        return self.contenu == []

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

    def depiler(self):
        """
        Retire et renvoie l'élément placé au sommet de la pile,
        si la pile n’est pas vide. Produit une erreur sinon.
        """
        assert 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 = ... + ...
            else:
                resultat = ...
            p.empiler(...)
    return ...

Exemples :

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

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• dico est un dictionnaire non vide : 1 <= len(dico) <= 10^4
• chaque clé de dico est une chaîne de caractères non vide d’au plus 20 caractères
• chaque valeur de dico est un entier v avec -10^6 <= v <= 10^6
• si plusieurs clés sont associées à la valeur maximale, la clé renvoyée est la première rencontrée dans l’ordre d’insertion du dictionnaire

Exercice 2

Contraintes :

• 1 <= len(tab) <= 10^4
• chaque élément de tab est soit un entier n avec -10^3 <= n <= 10^3, soit l’une des chaînes '+' ou '*'
• l’expression postfixe représentée par tab est toujours bien formée : le parcours se termine avec un unique élément dans la pile
• un tableau réduit à un seul entier, par exemple [7], est une expression postfixe valide
• la valeur renvoyée est un entier Python

Exercice 1 - le plus grand nombre de « like »

L’idée. On cherche la plus grande valeur du dictionnaire, mais il faut aussi retenir la clé qui va avec. On garde donc deux variables au lieu d’une : valeur_max, le plus grand nombre de « like » vu jusqu’ici, et cle_max, le pseudo qui lui correspond. On parcourt les clés du dictionnaire et, chaque fois qu’on tombe sur une valeur strictement plus grande que valeur_max, on met les deux variables à jour ensemble.

Le piège est le point de départ. On ne part pas de 0, parce que les valeurs peuvent être négatives : on partirait alors avec un maximum déjà trop grand. Comme l’énoncé garantit que le dictionnaire n’est pas vide, on part de sa première clé, qui est forcément une réponse possible.

Un petit exemple. Pour {'Alan': 222, 'Ada': 201, 'Eve': 222}, on part de ('Alan', 222). Ensuite 201 n’est pas plus grand, et le 222 d’Eve n’est pas plus grand non plus : il est égal. Rien ne bouge, on renvoie bien ('Alan', 222).

def max_dico(dico):
    cles = list(dico)
    cle_max = cles[0]
    valeur_max = dico[cle_max]
    for cle in cles:
        # Comparaison stricte : en cas d'égalité, on garde la clé rencontrée en premier
        if dico[cle] > valeur_max:
            cle_max = cle
            valeur_max = dico[cle]
    return (cle_max, valeur_max)

Explications. cles est la liste des clés dans leur ordre d’insertion, et cles[0] sert de point de départ. Dans la boucle, dico[cle] est la valeur associée à la clé courante. Le > plutôt que >= est le détail qui fait passer le deuxième exemple : avec >=, Eve remplacerait Alan et on renverrait ('Eve', 222), ce qui n’est pas la première valeur maximale. On renvoie enfin les deux variables dans un tuple, dans l’ordre demandé : la clé puis la valeur.

Exercice 2 - évaluer une expression postfixe

L’idée. L’énoncé décrit exactement l’algorithme, il faut le traduire en Python. On parcourt le tableau de gauche à droite avec une pile. Un élément du tableau est soit un nombre, soit un opérateur, et il n’y a que deux cas à traiter :

• si c’est un nombre, on l’empile et on passe au suivant ;
• si c’est un opérateur, ses deux opérandes sont justement les deux valeurs au sommet de la pile : on les dépile, on applique l’opération, et on empile le résultat.

À la fin, la pile contient une seule valeur, celle de l’expression : on la dépile et on la renvoie.

Un petit exemple. Pour [2, 3, '+', 5, '*'], la pile évolue ainsi : on empile 2, puis 3 ; le '+' dépile 3 et 2 et empile 5 ; on empile 5 ; le '*' dépile 5 et 5 et empile 25. Il reste 25, qu’on renvoie.

def eval_expression(tab):
    p = Pile()
    for element in tab:
        if element != '+' and element != '*':
            p.empiler(element)
        else:
            # Les deux opérandes sont au sommet de la pile ; + et * étant commutatifs,
            # l'ordre des deux dépilements n'a pas d'importance
            if element == '+':
                resultat = p.depiler() + p.depiler()
            else:
                resultat = p.depiler() * p.depiler()
            p.empiler(resultat)
    return p.depiler()

Explications. Le test element != '+' and element != '*' se lit « ce n’est ni un plus ni une étoile », donc c’est un nombre : le seul trou à combler sur cette ligne était le and. Attention, un or à cet endroit serait toujours vrai et on empilerait aussi les opérateurs.

p.depiler() + p.depiler() fait bien les deux dépilements demandés par l’énoncé, l’un après l’autre. Ici l’ordre n’a pas d’importance parce que l’addition et la multiplication donnent le même résultat dans les deux sens ; avec une soustraction ou une division il aurait fallu stocker chaque valeur dépilée dans sa propre variable, en faisant attention à quel opérande est en haut de la pile.

Enfin, return p.depiler() récupère l’unique valeur restante. On n’écrit pas return p, qui renverrait la pile elle-même et non un nombre. Ce return explique aussi le cas d’un tableau réduit à un seul nombre, comme [7] : on empile 7, la boucle se termine, et on le dépile aussitôt pour le renvoyer.