Corrigé exercice 1 NSI jour 2 Liban-Mayotte 2022

La notation polonaise inverse est utilisée dans le langage de programmation Postscript.

notation classique	notation NPI	Postscript
`3 + 9`	`3 9 +`	`3 9 add`
`8 × (3+5)`	`8 3 5 + ×`	`8 3 5 add mul`
`(17+5) × 4`	`17 5 + 4 ×`	`17 5 add 4 mul`

Le passage de la première colonne à l'une des deux autres s'appelle la compilation. Elle est l'objet du sujet d'agrégation d'informatique 2022 (épreuve 3).

Exemple

7 × (3+25) se compile en 7 3 25 + × (en Postscript 7 3 25 add mul) et s'« exécute » ainsi :

7 3 25 + ×

étape

pile

Pour l'expression compilée 12 4 5 × + on a

12 4 5 × +

étape

pile
On a la fonction top suivante :
```
def top(p):
    x = depiler(p)
    empiler(p,x)
    return x
```
qui ne modifie pas la pile mais permet de voir son dessus quand même.
1. Après
```
temp = top(p1)
```
  la variable temp contient le haut de p1 (soit 25 dans l'exemple).
2. Après cette exécution la pile p1 n'a pas changé et est donc toujours
  
  25
  
  3
  
  7

def addition(p):
    a = depiler(p)
    b = depiler(p)
    empiler(p,a+b)

Avec
```
def multiplication(p):
    a = depiler(p)
    b = depiler(p)
    empiler(p,a*b)
```
on peut calculer (3+5)×7 qui se compile en 3 5 + 7 × par:
```
p = pile_vide()
empiler(p,3)
empiler(p,5)
additionner(p)
empiler(p,7)
multiplier(p)
print(top(p))
```
3 5 + 7 ×

étape

pile