Sujet NSI — Terminale — Liban — Bac 2022

EXERCICE 1 (4 points) Cet exercice porte sur les structures de données (pile). La notation polonaise inverse (NPI) permet d'écrire des expressions de calculs numériques sans utiliser de parenthèse. Cette manière de présenter les calculs a été utilisée dans des calculatrices de bureau dès la fin des années 1960. La NPI est une forme d’écriture d’expressions algébriques qui se distingue par la position relative que prennent les nombres et leurs opérations. Par exemple : Notation classique Notation NPI 3+9 3 9 + 8×(3+5) 8 3 5 + × (17+5)×4 17 5 + 4 × L’expression est lue et évaluée de la gauche vers la droite en mettant à jour une pile. • Les nombres sont empilés dans l’ordre de la lecture. • Dès la lecture d’un opérateur (+, -, ×, /), les deux nombres au sommet de la pile sont dépilés et remplacés par le résultat de l’opération effectuée avec ces deux nombres. Ce résultat est ensuite empilé au sommet de la pile. A la fin de la lecture, la valeur au sommet est renvoyée. Exemple : l’expression 7 3 25 + × qui correspond au calcul 7×(3+25) s’évalue à 196 comme le montrent les états successifs de la pile créée, nommée p : • On empile la valeur 7. • On empile la valeur 3. • On empile la valeur 25. • On remplace les deux nombres du sommet de la pile (25 et 3) par leur somme 28. • On remplace les deux nombres du sommet de la pile (28 et 7) par leur produit 196. Schéma descriptif des différentes étapes d’exécution. 7 3 25 + × 25 3 3 28 7 7 7 7 196 p p p p p p 1. En vous inspirant de l’exemple ci-dessus, dessiner le schéma descriptif de ce que donne l’évaluation par la NPI de l’expression 12 4 5 × + . 22-NSIJ2LR1 Page 2 sur 13 2. On dispose de la pile suivante nommée p1 : 25 3 7 p1 On rappelle ci-dessous les primitives de la structure de pile (LIFO : Last In First out) : Fonction Description pile_vide() Créé et renvoie une nouvelle pile vide empiler(p, e) Place l’élément e au sommet de la pile p. depiler(p) Supprime et renvoie l’élément se trouvant au sommet de p. est_vide(p) Renvoie un booléen indiquant si p est vide ou non. On dispose aussi de la fonction suivante, qui prend en