====== Transformer une expression en notation polonaise inversée ======

Partons d'une expression écrite sous la forme ''%%7 * 6 + 4 *(15+2)%%''.

Si vous avez fait l'exercice sur la [[nsi:tds:maths:calcnpi|Calculatrice en notation polonaise inversée]], vous savez qu'il est possible d'écrire cette expression sous une forme qui rend l'ordre d'exécution plus facile à déterminer pour une machine : ''%%7 6 * 4 15 2 + * +%%''. C'est la notation polonaise inversée.

Dans l'exercice sur la notation polonaise inversée, vous avez vu comment évaluer une expression donnée sous cette forme. La difficulté consiste à produire la forme polonaise inversée à partir de la forme normale.

Je vous donne un algorithme faisant ce travail. Je ne détaille pas plus et vous laisse y réfléchir.

<code lang-none linenums>
FONCTION to_npi
ENTRÉE: liste représentant l'expression en notation normale
SORTIE: liste représentant l'expression en notation polonaise inversée (npi)
DÉBUT
    créer une pile pile_op vide
    créer sortie, une liste vide
    POUR CHAQUE item DANS liste
        SI item est un nombre ALORS
            placer item en bout de sortie
        SINON SI item est ( ALORS
            empiler item dans pile_op
        SINON SI item est ) ALORS
            TANT QUE pile_op non vide ET sommet pile_op différent de (
                dépiler pile_op et placer l'item obtenu au bout de sortie
            FIN
        SINON
            dans ce cas item est + - ou *
            TANT QUE pile_op non vide ET sommet pile_op est opérande plus prioritaire que item
                dépiler pile_op et placer l'item obtenu au bout de sortie
            empiler item dans pile_op
        FIN
    TANT QUE pile_op non vide
        dépiler pile_op, soit op le résultat
        SI op différent de ( ALORS
            ajouter op en bout de sortie
        FIN
    FIN
    RENVOYER sortie
FIN
</code>

Cet algorithme parait complexe mais c'est à peu près ce que vous faites quand vous lisez une expression : Vous la parcourez et vous laissez de côté certains opérateurs en attendant la suite, pour voir s'il n'y en a pas un plus prioritaire plus loin. Par exemple, dans ''%%3 * 2 + 4%%'', vous devez laisser ''%%*%%'' de côté jusqu'à voir le ''%%+%%'' qui vous permet de savoir que vous pouvez exécuter le ''%%*%%''...

<WRAP box>Implémentez cette fonction en Python et testez.

Test possible :
<code python>
mon_expression = [7, '*', 6, '+', 4, '*', '(', 15, '+', 2, ')']"
npi = to_npi(mon_expression)
print(npi) # devrait afficher [7, 6, '*', 4, 15, 2, '+', '*', '+']
</code>
</WRAP>