Problème — Évaluation d'une expression en notation postfixée

On parcourt les jetons (tokens). Un nombre est empilé ; un opérateur dépile ses deux opérandes, calcule, et empile le résultat. À la fin, la pile contient l'unique valeur du résultat.

def evaluer_postfixe(expr):
    pile = []
    for jeton in expr.split():          # decoupe selon les espaces
        if jeton in ("+", "-", "*", "/"):
            droite = pile.pop()          # second operande
            gauche = pile.pop()          # premier operande
            if jeton == "+":
                pile.append(gauche + droite)
            elif jeton == "-":
                pile.append(gauche - droite)
            elif jeton == "*":
                pile.append(gauche * droite)
            else:
                pile.append(gauche / droite)
        else:
            pile.append(float(jeton))    # un nombre : on empile
    return pile.pop()                    # resultat final

# Tests
print(evaluer_postfixe("3 4 + 5 *"))     # 35.0
print(evaluer_postfixe("10 2 / 3 -"))    # 2.0

La pile mémorise les résultats intermédiaires, exactement comme la pile d'exécution d'un calcul. L'expression étant parcourue une fois et chaque opération de pile coûtant $O(1)$, le coût total est $O(n)$, où $n$ est le nombre de jetons.