🧮 Évaluation arithmétique
🧮 On considère ici des arbres syntaxiques d'expression arithmétique simple.
Premier exemple
L'expression A définie avec y + 12 peut être représentée par l'arbre
graph TB
R("'+'")
R --> R0("'y'")
R --> R1("'12'")A = ['+', [
['y', []],
['12', []],
]
Si on donne la valeur de y, on peut évaluer A.
Par exemple, avec y = 5, on a A évalué en 5 + 12 = 17.
Expression arithmétique simple
Pour simplifier et garder réaliste le problème, on ne considère ici que les expressions mathématiques entre opérandes entières et dont le résultat est entier. On ne considère que quelques opérateurs dans cet exercice.
'+': le plus binaire entre deux opérandes'-': le moins binaire entre deux opérandes'*': le multiplication entre deux opérandes'//': la division entière entre deux opérandes'%': le reste dans la division entière (le modulo)'**': la puissance entre deux opérandes, avec exposant positif'+': le plus unaire qui n'a qu'un opérande'-': le moins unaire qui n'a qu'un opérande
Pour cet exercice, il est inutile de connaitre les règles de priorités, elles sont imposées par la construction de l'arbre qui vous est donné. L'objectif est de l'évaluer étant donné un contexte ; un dictionnaire qui donne les valeurs des variables.
Le moins et le plus unaire
- Dans une expression comme
-x+2, le-est unaire, ce n'est pas une soustraction, c'est l'opérateur qui renvoie l'opposé de son opérande. - Dans une expression comme
5**+2, le+est unaire, ce n'est pas une addition, c'est l'opérateur qui renvoie son opérande inchangé.
Nœuds de l'arbre
Dans un arbre syntaxique d'expression arithmétique simple, un nœud est :
- soit un opérateur binaire, il a alors deux sous-arbres : ses opérandes
- soit un opérateur unaire, il a alors un seul sous-arbres : son opérande
- soit une variable, il n'a alors aucun sous-arbre
- soit une valeur entière (sous forme de chaine de caractères), il n'a alors aucun sous-arbre
- il pourrait y avoir des opérateurs ternaires (ou plus ...) mais pas dans cet exercice
Astuces
Pour reconnaitre un opérateur binaire d'un opérateur unaire, il suffit de regarder le nombre de sous-arbres.- Pour reconnaitre une variable d'une valeur, il suffit de vérifier si c'est une clé du dictionnaire de contexte. On garantit que si ce n'est pas une clé du dictionnaire, alors ce sera une valeur entière.
- Pour transformer une chaine de caractères en entier, on peut utiliser la fonction
int; ainsiint('12')renvoie l'entier12.
Second exemple
graph TB
R("'*'")
R --> N1("'+'")
R --> N2("'//'")
N1 --> N3("'-'")
N1 --> N4("'3'")
N2 --> N5("'b'")
N2 --> N6("'2'")
N3 --> N7("'a'")Cet arbre représente l'expression (-a + 3) * (b // 2).
Avec a = 6 et b = 7, l'évaluation donne -9.
Exercice
Coder une fonction évaluation qui prend en arguments
- un
arbrereprésentant une expression mathématique simple - un dictionnaire
contextequi permet d'associer à une variable une valeur entière.
et qui renvoie l'évaluation de l'expression mathématique suivant ce contexte.
On garantit que l'exposant des puissances sera toujours positif, et ainsi tous les résultats même intermédiaires seront des entiers. On garantit également qu'il n'y aura pas de division par zéro.
Bref, l'exercice est prévu pour un cadre simple, mais généralisable.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)