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

Si vous avez fait l'exercice sur la 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.

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

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 *…

mon_expression = [7, '*', 6, '+', 4, '*', '(', 15, '+', 2, ')']"
npi = to_npi(mon_expression)
print(npi) # devrait afficher [7, 6, '*', 4, 15, 2, '+', '*', '+']