Parser une expression mathématique en Python : AST, piles et shunting-yard

Parser une expression mathématique en Python, ce n’est pas seulement calculer "2 + 3 * 4". C’est transformer une chaîne de caractères en une structure que le programme comprend : tokens, arbre syntaxique, notation postfixée ou pile d’exécution.

La tentation rapide est d’utiliser eval. Pour un test local, cela peut sembler pratique. Pour une entrée utilisateur, c’est une mauvaise idée : eval exécute du code Python, pas seulement des calculs. Si vous voulez accepter une formule saisie par quelqu’un, il faut contrôler la grammaire autorisée.

Il existe trois approches utiles :

• utiliser ast.parse() avec une liste blanche de noeuds autorisés ;
• écrire un petit parser à piles pour apprendre les priorités ;
• convertir l’expression en notation postfixée avec l’algorithme shunting-yard.

La réponse courte

Si votre expression suit la syntaxe Python, utilisez ast.parse(..., mode="eval"), puis évaluez seulement les noeuds que vous autorisez.

import ast
import operator


OPERATEURS = {
    ast.Add: operator.add,
    ast.Sub: operator.sub,
    ast.Mult: operator.mul,
    ast.Div: operator.truediv,
    ast.FloorDiv: operator.floordiv,
    ast.Mod: operator.mod,
    ast.Pow: operator.pow,
}

UNAIRES = {
    ast.UAdd: operator.pos,
    ast.USub: operator.neg,
}


def evaluer_expression(expression):
    arbre = ast.parse(expression, mode="eval")
    return evaluer_noeud(arbre.body)


def evaluer_noeud(noeud):
    if isinstance(noeud, ast.Constant) and isinstance(noeud.value, (int, float)):
        return noeud.value

    if isinstance(noeud, ast.BinOp) and type(noeud.op) in OPERATEURS:
        gauche = evaluer_noeud(noeud.left)
        droite = evaluer_noeud(noeud.right)
        return OPERATEURS[type(noeud.op)](gauche, droite)

    if isinstance(noeud, ast.UnaryOp) and type(noeud.op) in UNAIRES:
        return UNAIRES[type(noeud.op)](evaluer_noeud(noeud.operand))

    raise ValueError(f"Expression non autorisée : {type(noeud).__name__}")


print(evaluer_expression("2 + 3 * 4"))   # 14
print(evaluer_expression("-(10 + 2)"))   # -12

Ce code n’autorise que des nombres, des opérateurs arithmétiques binaires et les signes + / - unaires. Il refuse les appels de fonctions, les imports, les attributs, les variables et tout le reste.

Pour une calculatrice pédagogique, c’est une base plus propre que eval.

Pourquoi éviter eval pour parser une expression

eval évalue une expression Python complète. Le problème est dans le mot “Python”. Une chaîne de caractères n’est pas traitée comme une simple formule mathématique, mais comme du code.

expression = "2 + 3 * 4"
print(eval(expression))  # 14

Cet exemple est correct parce que l’expression est écrite par vous. Mais dès que la chaîne vient d’un formulaire, d’un fichier, d’une API ou d’un utilisateur, vous devez supposer qu’elle peut contenir autre chose qu’un calcul.

La bonne question n’est donc pas : “comment calculer une chaîne ?”
La bonne question est : “quelle grammaire ai-je le droit d’accepter ?”

Pour une calculatrice simple, vous pouvez autoriser :

• les entiers et les décimaux ;
• les parenthèses ;
• +, -, *, /, éventuellement //, % et ** ;
• quelques fonctions choisies, si vous les ajoutez explicitement.

Tout le reste doit être refusé.

Ce que signifie parser une expression

Une expression comme :

2 + 3 * 4

n’est pas seulement une suite de caractères. Elle possède une structure :

2 + (3 * 4)

La multiplication est évaluée avant l’addition. Un parseur doit donc comprendre les priorités d’opérateurs, les parenthèses et l’ordre de lecture.

Un parseur fait généralement plusieurs étapes :

La tokenisation de "2 + 3 * 4" donne par exemple :

[2, "+", 3, "*", 4]

Ensuite, le parseur doit comprendre que 3 * 4 doit être calculé avant 2 + ....

Approche 1 : utiliser ast.parse avec une liste blanche

Le module ast transforme du code Python en arbre syntaxique abstrait. Pour une expression, on utilise mode="eval".

import ast

arbre = ast.parse("2 + 3 * 4", mode="eval")

print(ast.dump(arbre, indent=4))

Sortie simplifiée :

Expression(
    body=BinOp(
        left=Constant(value=2),
        op=Add(),
        right=BinOp(
            left=Constant(value=3),
            op=Mult(),
            right=Constant(value=4))))

Ce résultat montre bien la structure :

2 + (3 * 4)

Le noeud principal est une addition. Sa partie droite est une multiplication.

Un évaluateur AST contrôlé

Voici une version plus complète, avec quelques protections simples :

import ast
import operator


OPERATEURS = {
    ast.Add: operator.add,
    ast.Sub: operator.sub,
    ast.Mult: operator.mul,
    ast.Div: operator.truediv,
    ast.FloorDiv: operator.floordiv,
    ast.Mod: operator.mod,
    ast.Pow: operator.pow,
}

UNAIRES = {
    ast.UAdd: operator.pos,
    ast.USub: operator.neg,
}


def calculer(expression):
    arbre = ast.parse(expression, mode="eval")
    return calculer_noeud(arbre.body)


def calculer_noeud(noeud):
    if isinstance(noeud, ast.Constant):
        if isinstance(noeud.value, (int, float)):
            return noeud.value
        raise ValueError("Seuls les nombres sont autorisés")

    if isinstance(noeud, ast.UnaryOp) and type(noeud.op) in UNAIRES:
        return UNAIRES[type(noeud.op)](calculer_noeud(noeud.operand))

    if isinstance(noeud, ast.BinOp) and type(noeud.op) in OPERATEURS:
        gauche = calculer_noeud(noeud.left)
        droite = calculer_noeud(noeud.right)

        if isinstance(noeud.op, ast.Pow) and abs(droite) > 100:
            raise ValueError("Puissance trop grande")

        return OPERATEURS[type(noeud.op)](gauche, droite)

    raise ValueError(f"Noeud interdit : {type(noeud).__name__}")


print(calculer("2 + 3 * 4"))      # 14
print(calculer("(2 + 3) * 4"))    # 20
print(calculer("-5 + 2 ** 3"))    # 3

L’intérêt de cette approche est que Python s’occupe déjà de la grammaire, des parenthèses et des priorités. Vous vous concentrez sur ce que vous acceptez ou refusez.

Ce que cette approche refuse

Le code ci-dessus refuse les appels de fonctions :

calculer("max(1, 2)")

Il refuse aussi les variables :

calculer("x + 2")

Il refuse les chaînes :

calculer("'hello'")

C’est volontaire. Un parseur sûr commence petit, puis ajoute des fonctionnalités une par une.

ast.literal_eval n’est pas fait pour les formules

On voit parfois ast.literal_eval présenté comme une alternative sûre à eval. C’est vrai pour des littéraux Python simples : listes, dictionnaires, chaînes, nombres, booléens.

Mais ce n’est pas un parseur de formules arithmétiques.

import ast

print(ast.literal_eval("[1, 2, 3]"))  # [1, 2, 3]
print(ast.literal_eval("2 + 3"))      # ValueError

Utilisez ast.literal_eval pour lire une valeur littérale. Pour évaluer une formule mathématique, utilisez un AST contrôlé ou un parser dédié.

Approche 2 : parser avec deux piles

Pour comprendre le mécanisme, on peut écrire un parseur à piles. L’idée est classique :

• une pile pour les valeurs ;
• une pile pour les opérateurs ;
• une règle de priorité pour savoir quand calculer.

Voici une version volontairement limitée à +, -, *, / et aux parenthèses.

import operator
import re


OPERATEURS = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "/": operator.truediv,
}

PRIORITE = {
    "+": 1,
    "-": 1,
    "*": 2,
    "/": 2,
}

TOKEN_RE = re.compile(r"\s*(?:(\d+(?:\.\d+)?)|(.))")


def tokenizer(expression):
    for nombre, autre in TOKEN_RE.findall(expression):
        if nombre:
            yield float(nombre) if "." in nombre else int(nombre)
        elif autre in OPERATEURS or autre in "()":
            yield autre
        else:
            raise ValueError(f"Token invalide : {autre}")


def appliquer_operateur(valeurs, operateurs):
    operateur = operateurs.pop()
    droite = valeurs.pop()
    gauche = valeurs.pop()
    valeurs.append(OPERATEURS[operateur](gauche, droite))


def evaluer_avec_piles(expression):
    valeurs = []
    operateurs = []

    for token in tokenizer(expression):
        if isinstance(token, (int, float)):
            valeurs.append(token)

        elif token == "(":
            operateurs.append(token)

        elif token == ")":
            while operateurs and operateurs[-1] != "(":
                appliquer_operateur(valeurs, operateurs)
            if not operateurs:
                raise ValueError("Parenthèse fermante sans ouvrante")
            operateurs.pop()

        elif token in OPERATEURS:
            while (
                operateurs
                and operateurs[-1] in OPERATEURS
                and PRIORITE[operateurs[-1]] >= PRIORITE[token]
            ):
                appliquer_operateur(valeurs, operateurs)
            operateurs.append(token)

    while operateurs:
        if operateurs[-1] == "(":
            raise ValueError("Parenthèse ouvrante non fermée")
        appliquer_operateur(valeurs, operateurs)

    if len(valeurs) != 1:
        raise ValueError("Expression invalide")

    return valeurs[0]


print(evaluer_avec_piles("2 + 3 * 4"))      # 14
print(evaluer_avec_piles("(2 + 3) * 4"))    # 20

Cette approche montre le coeur du parsing arithmétique : tant que l’opérateur déjà en pile est plus prioritaire ou aussi prioritaire que le nouvel opérateur, on l’applique.

Approche 3 : convertir en notation postfixée avec shunting-yard

L’algorithme shunting-yard transforme une expression infixée :

2 + 3 * 4

en notation postfixée, aussi appelée RPN :

2 3 4 * +

Dans cette notation, les opérateurs arrivent après leurs opérandes. Cela rend l’évaluation très simple avec une pile.

Convertir une expression en RPN

import re


PRIORITE = {
    "+": 1,
    "-": 1,
    "*": 2,
    "/": 2,
}

TOKEN_RE = re.compile(r"\s*(?:(\d+(?:\.\d+)?)|(.))")


def tokenizer(expression):
    for nombre, autre in TOKEN_RE.findall(expression):
        if nombre:
            yield float(nombre) if "." in nombre else int(nombre)
        elif autre in PRIORITE or autre in "()":
            yield autre
        else:
            raise ValueError(f"Token invalide : {autre}")


def vers_rpn(expression):
    sortie = []
    operateurs = []

    for token in tokenizer(expression):
        if isinstance(token, (int, float)):
            sortie.append(token)

        elif token in PRIORITE:
            while (
                operateurs
                and operateurs[-1] in PRIORITE
                and PRIORITE[operateurs[-1]] >= PRIORITE[token]
            ):
                sortie.append(operateurs.pop())
            operateurs.append(token)

        elif token == "(":
            operateurs.append(token)

        elif token == ")":
            while operateurs and operateurs[-1] != "(":
                sortie.append(operateurs.pop())
            if not operateurs:
                raise ValueError("Parenthèse fermante sans ouvrante")
            operateurs.pop()

    while operateurs:
        if operateurs[-1] == "(":
            raise ValueError("Parenthèse ouvrante non fermée")
        sortie.append(operateurs.pop())

    return sortie


print(vers_rpn("2 + 3 * 4"))      # [2, 3, 4, '*', '+']
print(vers_rpn("(2 + 3) * 4"))    # [2, 3, '+', 4, '*']

Évaluer la notation postfixée

Une fois l’expression convertie, l’évaluation tient en quelques lignes.

import operator


OPERATEURS = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "/": operator.truediv,
}


def evaluer_rpn(tokens):
    pile = []

    for token in tokens:
        if isinstance(token, (int, float)):
            pile.append(token)
        else:
            droite = pile.pop()
            gauche = pile.pop()
            pile.append(OPERATEURS[token](gauche, droite))

    if len(pile) != 1:
        raise ValueError("Expression postfixée invalide")

    return pile[0]


rpn = vers_rpn("2 + 3 * 4")
print(rpn)               # [2, 3, 4, '*', '+']
print(evaluer_rpn(rpn))  # 14

Shunting-yard est particulièrement intéressant si vous voulez séparer clairement deux étapes :

1. transformer l’expression en forme intermédiaire ;
2. évaluer cette forme ensuite.

Cette séparation rend le code plus testable.

Gérer le signe moins unaire

Les exemples précédents gèrent 2 - 3, mais pas forcément -3 + 2 ou 2 * -3. Le signe moins unaire est l’une des premières difficultés quand on écrit son propre parser.

Il faut distinguer :

5 - 2   # soustraction
-2      # nombre négatif ou opérateur unaire

Avec ast, Python le fait déjà :

print(calculer("-3 + 2"))      # -1
print(calculer("2 * -3"))      # -6

Avec un parser maison, vous devez ajouter une règle. Par exemple : si - arrive au début de l’expression, après ( ou après un autre opérateur, il peut être traité comme un signe unaire.

Pour un tutoriel ou un exercice, vous pouvez commencer sans le moins unaire, puis l’ajouter ensuite. Pour du code en production, ce cas doit être prévu dès la conception.

Ajouter des fonctions comme sin, cos ou sqrt

Un parseur de calculatrice finit souvent par accepter des fonctions :

sqrt(9) + sin(0)

Avec ast, vous pouvez autoriser explicitement certains appels.

import ast
import math


FONCTIONS = {
    "sqrt": math.sqrt,
    "sin": math.sin,
    "cos": math.cos,
}


def calculer_appel(noeud):
    if not isinstance(noeud.func, ast.Name):
        raise ValueError("Appel interdit")

    nom = noeud.func.id

    if nom not in FONCTIONS:
        raise ValueError(f"Fonction interdite : {nom}")

    arguments = [calculer_noeud(arg) for arg in noeud.args]
    return FONCTIONS[nom](*arguments)

Il faut ensuite appeler calculer_appel dans votre évaluateur quand vous rencontrez un ast.Call.

L’idée importante : ne donnez jamais accès à toutes les fonctions. Créez une liste blanche courte.

Quand choisir AST, piles ou shunting-yard ?

Pour un blog, un exercice ou une calculatrice simple, ast est souvent le meilleur compromis. Pour apprendre les algorithmes, shunting-yard est plus formateur, car il oblige à gérer les priorités et les parenthèses.

Erreurs fréquentes

Découper l’expression avec split

split() fonctionne seulement si tous les espaces sont parfaits.

print("2 + 3".split())   # ['2', '+', '3']
print("2+3".split())     # ['2+3']

Pour parser une expression, utilisez un vrai tokenizer.

Oublier la priorité des opérateurs

Si vous lisez simplement de gauche à droite, vous obtiendrez :

2 + 3 * 4 = 20

Alors que le résultat correct est :

2 + (3 * 4) = 14

La priorité des opérateurs est la raison principale d’un parser.

Ne pas vérifier les parenthèses

Une expression comme :

(2 + 3 * 4

doit être refusée. Ne laissez pas votre programme produire un résultat silencieux sur une expression incomplète.

Autoriser trop de choses dans l’AST

ast.parse ne suffit pas à rendre une expression sûre. Il faut inspecter l’arbre et refuser tout ce qui n’est pas explicitement autorisé.

Un bon parseur sûr est restrictif par défaut.

Ignorer les limites de calcul

Même une expression purement mathématique peut poser problème :

9 ** 999999999

Ce n’est pas une injection de code, mais cela peut consommer beaucoup de ressources. Si votre parseur est exposé à des utilisateurs, ajoutez des limites : longueur maximale, profondeur maximale, puissance maximale, nombre maximal de tokens.

Tester un parseur d’expression

Un parseur se teste avec des cas simples, des cas de priorité et des erreurs attendues.

def test_calculer():
    assert calculer("2 + 3") == 5
    assert calculer("2 + 3 * 4") == 14
    assert calculer("(2 + 3) * 4") == 20
    assert calculer("-5 + 2") == -3

Ajoutez aussi des tests d’erreur :

def doit_echouer(expression):
    try:
        calculer(expression)
    except ValueError:
        return True
    return False


assert doit_echouer("x + 2")
assert doit_echouer("'hello'")

Ces tests évitent de transformer votre parser en mini-interpréteur Python sans vous en rendre compte.

Pour aller plus loin

Parser une expression mathématique est un excellent exercice, car il combine chaînes de caractères, piles, arbres, récursion, priorités et sécurité. La bonne solution dépend du besoin : ast pour exploiter la grammaire Python de manière contrôlée, piles pour apprendre, shunting-yard pour produire une notation intermédiaire claire.

Pour continuer dans le même cluster Python :

• Complexité algorithmique en Python : comprendre O(n), O(log n) et O(n²)
• XOR en Python : opérateur ^, table de vérité et exemples bitwise
• Modulo en Python : comprendre %, // et divmod avec exemples

La règle à retenir : ne parsez pas une expression utilisateur avec eval. Définissez ce qui est autorisé, transformez la chaîne en structure contrôlée, puis évaluez seulement cette structure.

Références

• Documentation Python officielle : ast, arbres syntaxiques abstraits
• Documentation Python officielle : expressions et priorité des opérateurs
• Documentation Python officielle : operator, opérateurs sous forme de fonctions