Expressions arithmétiques

Les expressions arithmétiques sont équivalentes à des arbres binaires dont

• les feuilles sont des valeurs
• les noeuds internes sont des opérations binaires (+,-,*,/)
• aucun noeud n'est de degré 1

# Arbre équivalent à l'expression (a*(b+c))

R        = t = Noeud('*')
t.gauche = a = Noeud('a')
t.droite = p = Noeud('+')
p.gauche = b = Noeud('b')
p.droite = c = Noeud('c')
h.afficher_arbre_binaire(R)

Notation infixée

Elle correspond à la manière usuelle d'écrire les expressions arithmétiques.

Les opérandes d'une opération entourent son symbole.

Cela correspond donc à un parcours symétrique de l'arbre.

def expr_infixe(R):
    assert(R != None)
    str = ""
    if R.gauche: str += "(" + expr_infixe(R.gauche)
    str += "{}".format(R)
    if R.droite: str += expr_infixe(R.droite) + ")"
    return str

h.afficher_arbre_binaire(R)

# Quelle est l'expression infixe correspondante?

infixe = expr_infixe(R); print(infixe)

(a*(b+c))

Notation pré-fixée

Cette notation correspond au parcours pré-ordonné de l'arbre de l'expression.

Elle est aussi connue sous le nom de notation de Łukasiewicz ou notation polonaise.

def expr_prefixe(R):
    str = ""
    if R:
        str += "{} ".format(R)
        str += expr_prefixe(R.gauche)
        str += expr_prefixe(R.droite)
    return str

h.afficher_arbre_binaire(R)

# Quelle est l'expression pré-fixée correspondante?

prefixe = expr_prefixe(R); print(prefixe)

* a + b c 

Elle ne nécessite pas de parenthèse dès lors que chaque opérateur a un nombre fixe d'opérandes.

Elle est utilisée (avec parentèses) pour la syntaxe du langage Common Lisp.

Notation post-fixée

Elle correspond au parcours post-ordonné de l'arbre de l'expression.

Aussi connue sous le nom de notation polonaise inverse

def expr_postfixe(R):
    str = ""
    if R:
        str += expr_postfixe(R.gauche)
        str += expr_postfixe(R.droite)
        str += "{} ".format(R)
    return str

h.afficher_arbre_binaire(R)

# Quelle est l'expression post-fixée correspondante?

postfixe = expr_postfixe(R); print(postfixe)

a b c + * 

Elle présente l'avantage par rapport à la notation infixe de toujours disposer des opérandes quand on atteint le symbole de l'opérateur, ce qui permet de l'évaluer directement.

Elle est utilisée par exemple dans les calculatrices HP ou dans le langage PostScript.

Expression → arbre

Il est évidemment possible d'effectuer l'opération inverse, qui convertit une expression préfixe, postfixe ou infixe en arbre.

On lit depuis un flux de charactères en entrée et on retourne la racine de l'arbre généré.

On utilise la fonction annexe suivante pour simplifier

def est_un_operateur(c):
    return "+-*/".find(c) != -1

Le flux d'un expression préfixe contient

• pour les opérateurs +-*/: la racine, puis le sous-arbre gauche, puis le sous-arbre droit

• pour les autres symboles: une feuille de l'arbre

Cela définit les cas général et trivial de la récursion

from io import StringIO
def prefixe_vers_arbre_str(chaine):
    s = chaine.replace(" ","")
    return prefixe_vers_arbre(StringIO(s))

def prefixe_vers_arbre(flux):
    c = flux.read(1)
    R = Noeud(c)
    if est_un_operateur(c):
        R.gauche = prefixe_vers_arbre(flux)
        R.droite = prefixe_vers_arbre(flux)
    return R

prefixe = "* - + a b / c d + e f"

# Quel est l'arbre correspondant ? 
# Quel est l'expression infixe correspondante ?

R2 = prefixe_vers_arbre_str(prefixe)
h.afficher_arbre_binaire(R2)
print(expr_infixe(R2))

(((a+b)-(c/d))*(e+f))

Infixe → arbre

On utilise le même prototype pour la conversion infixe vers arbre

Le flux d'un expression infixe contient soit

• une parenthèse (
  • suivie d'une expression infixe
  • suivie d'un opérateur +-*/
  • suivie d'une expression infixe
  • suivie d'une parenthèse )

• une feuille de l'arbre

Cela définit les cas général et trivial de la récursion

def infixe_vers_arbre_str(chaine):
    s = chaine.replace(" ","")
    return infixe_vers_arbre(StringIO(s))

def infixe_vers_arbre(flux):
    c = flux.read(1)
    if c == "(":
        R = Noeud("?")
        R.gauche = infixe_vers_arbre(flux) 
        R.etiquette = flux.read(1); 
        assert(est_un_operateur(R.etiquette))
        R.droite = infixe_vers_arbre(flux)
        c = flux.read(1);        
        assert(c == ")")
    else:
        R = Noeud(c)
    return R

infixe = "( (a*b) + ( (c*d) + (e/f) ) )"
# Quel est l'arbre correspondant ? 
# Quel est l'expression postfixe correspondante ?

R3 = infixe_vers_arbre_str(infixe)
h.afficher_arbre_binaire(R3)
print(expr_postfixe(R3))

a b * c d * e f / + + 

Postfixe → arbre

Cette conversion ne peut pas utiliser le même principe. Notamment parce qu'il n'y a pas de fin naturelle à une expression post-fixe. Il faut donc lire jusque la fin du flux.

Par contre, on peut utiliser une simple pile.

def postfixe_vers_arbre_str(chaine):
    s = chaine.replace(" ","")
    return postfixe_vers_arbre(StringIO(s))

def postfixe_vers_arbre(flux):
    Pile = []
    c = flux.read(1)
    while c != "":
        R = Noeud(c)
        if est_un_operateur(c): 
            R.droite = Pile.pop()
            R.gauche = Pile.pop()
        Pile.append(R)
        c = flux.read(1)
    return R

postfixe = "a b - c d e + * +"
# Quel est l'arbre correspondant ? 
# Quel est l'expression infixe correspondante ?

R4 = postfixe_vers_arbre_str(postfixe)
h.afficher_arbre_binaire(R4)
print(expr_infixe(R4))

((a-b)+(c*(d+e)))

ASD1 Notebooks on GitHub.io © Olivier Cuisenaire, 2018