TP - Évaluateur d'expressions

Introduction

Le but de ce TP sera de programmer un outil permettant d'évaluer une expression fournie comme une chaîne de caractères.

Par exemple 3 + 5 - 10 sera évaluée comme -2ou encore, si on sait que la variable avaut 3, alors l'expression 3*avaudra 9.

Dans un premier temps, les expressions n'admettront que des valeurs entières et pourront reconnaître

des constantes numériques
les opérateurs +, -,* et /
des variables
les parenthèses

Les variables suivront les conventions habituelles de Python, à savoir qu'elles ne peuvent commencer par un chiffre et sont uniquement composées de caractères alphanumériques et de _.

Première partie : la classe `Parser`

La classe Parser aura comme but de transformer une chaîne de caractères en ensemble de tokens utilisable par la suite. Un token est un élément constitutif d'une expression ; par exemple un opérateur, le nom d'une variable ou encore une valeur numérique.

Vous trouverez les tests unitaires propres à la classe Parser ici

1. Créer la classe `Parser`

Le constructeur de la classe prend en argument la liste des caractères spéciaux (hors caractères alphanumériques) admissibles pour former des tokens. Si aucune liste n'est fournie la valeur par défaut sera [ '+', '-', '*', '/', '_', '(', ')', ' ']. Cette liste est appelée alphabet et sera stockée dans un attribut d'instance.

2. Créer la méthode `is_in_alphabet`

Dans la classe Parser créer la méthode suivante

   is_in_alphabet(self, c: str) -> bool

qui renvoie True si le caractère c fait partie de l'alphabet ou s'il est de type alphanumérique et renvoie False sinon.

3. Créer la méthode `get_token`

Dans la classe Parser créer la méthode suivante

   get_token(self, flux: str) -> (str, str)

Cette méthode prend en entrée une chaîne de caractères appelée flux et renvoie comme résultat le premier token conforme à l'alphabet ainsi que le reste de flux, diminué du token lu.

Un token valide est :

un opérateur isolé parmi +, -, *, /, (, )
un nom de variable. Un nom de variable peut être d'une longueur quelconque, doit obligatoirement commencer par une lettre ou _ et est composée d'une combinaison de lettres, de chiffres et de _. Par exemple les tokens suivants sont des noms de variables valides : v _ _a v12_ vvv v1v2v3.

En revanche 6a ne l'est pas, puisqu'il commence par un chiffre.
un nombre. Un nombre est une suite de longueur quelconque et ininterrompue de chiffres.

La méthode get_token doit renvoyer les résultats suivants :

   p = Parser()

   flux1 = 'a + b'
   flux2 = ' a + b'
   flux3 = 'a+b'
   flux4 = 'abcd'
   flux5 = '12ab'
   flux6 = 'ab12'
   flux7 = '@ab'

   print(p.get_token(flux1)) # doit afficher ('a', ' + b')
   print(p.get_token(flux2)) # doit afficher ('a', ' + b')
   print(p.get_token(flux3)) # doit afficher ('a', '+b')
   print(p.get_token(flux4)) # doit afficher ('abcd', '')
   print(p.get_token(flux5)) # doit afficher ('12', 'ab')
   print(p.get_token(flux6)) # doit afficher ('ab12', '')
   print(p.get_token(flux7)) # doit afficher ('', '@ab')

4. Traiter une chaîne complète

Écrivez une méthode permettant de successivement extraire tous les tokens d'une chaîne de caractères en validant bien les conditions d'arrêt et le comportement en cas de caractères hors alphabet.

Seconde partie : la classe `Expression`

1. La classe `Expression`

On définit la classe Expression comme suit :

   class Expression:
       def eval(self) -> int:
           '''
           Evalue l'expression et calcule sa valeur
           :return: la valeur de l'expression 
           '''
           raise NotImplementedError

Cette définition correspond à une façon simpliste de déclarer une méthode abstraite.

2. Les classes dérivées

On dérivera ensuite la classe Expression en plusieurs sous-classes : Value, Variable, PrefixExpression, InfixExpression.

Pour chacune d'entre elles il sera nécessaire de définir a minima les méthodes suivantes :

un constructeur
une implémentation de la méthode eval()
une surcharge de la méthode __str__()

La méthode __str__() est une méthode prédéfinie dans Python indiquant comment un objet doit se comporter lorsqu'on souhaite le transformer en chaîne de caractères (notamment pour l'affichage). La signature de la fonction est

__str__(self) -> str

Vous pouvez vous référer à la documentation de Pyton pour plus de détails. L'utilisation de cette méthode est implicite dans la plupart des cas et on l'invoque rarement. Par exemple, dans le code suivant, print va automatiquement faire appel à __str__ pour l'affichage.

class MaClasse:

    def __str__(self) -> str:
        return "MaClasse"

if __name__ == "__main__":
    c = MaClasse()
    print(c)

Vous trouverez les tests unitaires propres aux classes Expression, Value et Variable ici

- La classe `Value`

La classe Value permettra de représenter les valeurs numériques.

son constructeur prend en argument un token ;
elle a un attribut d'instance nommé value de type int ;
le constructeur initialise l'attribut value avec celle représentée par le token fourni en entrée ;
la méthode __str()__ renvoie la chaîne de caractères représentant la valeur de l'attribut value.
la méthode eval() renvoie la valeur de l'attribut value.

- La classe `Variable`

La classe Value permettra de représenter des variables.

son constructeur prend en argument le nom de la variable
elle a un attribut name de type str et un attribut value de type ìnt.
le constructeur initialise l'attribut value à Ǹone (signifiant que la variable n'est pas initialisée) et initialise l'attribut name avec le token passé en fourni en entrée;
la méthode __str()__ renvoie la chaîne de caractères représentant la valeur de l'attribut name.
la méthode eval() renvoie la valeur de l'attribut value.

En plus de ces méthodes, la classe Variable possède la méthode set_value(int) qui permet d'attribuer une valeur à l'attribut value et qui ne renvoie pas de valeur.

- La classe `PrefixExpression`

La classe PrefixExpression permettra de représenter des expressions précédées d'un opérateur unaire, comme -5 ou -(5*x).

son constructeur prend en argument un token opérateur et une Expression qu'il stocke dans les attributs op de type str et expr de type Expression.
la méthode __str()__ renvoie la chaîne de caractères concaténant op et le résultat de expr.__str__().
la méthode eval() renvoie expr.eval() (polymorphisme) corrigé par op.

Vous trouverez les tests unitaires propres à la classe PrefixExpression ici

- La classe `InfixExpression`

De façon similaire la classe InfixExpression représente les Expression de type exp1 op exp2 comme 5 * 3 ou -6 + a.

son constructeur prend en argument un token opérateur et deux Expression qu'il stocke dans les attributs op de type str et expr1 et expr2 de type Expression.
la méthode __str()__ renvoie la chaîne de caractères concaténant op entre le résultat de expr1.__str__() et de expr2.__str__().
la méthode eval() renvoie le résultat de l'opérateur op aux opérandes gauche expr1.eval() et droite expr2.eval() (polymorphisme) corrigé par op.

Vous trouverez les tests unitaires propres à la classe InfixExpression ici

Troisième partie : combiner le tout

1. Créer la méthode `Parser.is_operator()`

Ajouter la méthode is_operator(op: str) -> bool dans la classe Parser. Cette méthode prend comme argument un token et retourne True s'il s'agit d'un opérateur, et False sinon.

2. Une solution imparfaite

Copiez et analysez le code ci-dessous. Complétez avec des commentaires et expliquez ce qu'il fait.

def read_expression(flot: str) -> (Expression, str):
    """
    :param variables:
    :param flot:
    :return:
    """
    p = Parser()

    token, flot = p.get_token(flot)
    previousExpression = None
    currentExpression = None

    while token:
        currentExpression = None

        if token.isnumeric():
            # Une expression non aboutie (= previousExpression is not None) ne peut pas être suivie d'un nombre sans
            # que les deux ne soient connectés par un opérateur.
            if previousExpression is not None:
                raise SyntaxError(token)
            currentExpression = Value(token)
        elif p.is_operator(token[0]):
            # Un opérateur est forément suivi d'une expression donc on va lire l'expression qui suit et
            # la stocker dans nextExpression.
            operator = token
            nextExpression, flot = read_expression(flot)

            # Selon l'existence ou on d'une expression précédent l'opérateur, on sera soit dans cas d'une
            # PrefixExpression ou d'une InfixExpression
            if not previousExpression:
                currentExpression = PrefixExpression(operator, nextExpression)
            else:
                currentExpression = InfixExpression(operator, previousExpression, nextExpression)

        elif token[0].isalpha() or token[0] == '_':
            # Une expression non aboutie (= previousExpression is not None) ne peut pas être suivie d'une variable sans
            # que les deux ne soient connectés par un opérateur.
            if previousExpression is not None:
                raise SyntaxError(token)
            currentExpression = Variable(token)

        else:
            raise NotImplementedError(token)

        previousExpression = currentExpression
        token, flot = p.get_token(flot)

    return currentExpression, flot

Ce code est une première approche d'un évaluateur d'expressions. Testez-le sur les exemples suivants et expliquez les résultats. Vous trouverez le test unitaire ici.

flow1 = "2 + 3"
flow2 = "2 + 3 - 5"
flow3 = "2 + 3 * 4"
flow4 = "3 * 4 + 2"
flow5 = "(3 * 4) + 2"
flow6 = "3 + a"

Quatrième partie : aller jusqu'au bout

1. Gérer les variables

a. Modifiez la fonction `read_expression()` (une première fois)

Modifiez la fonction read_expression(str) de sorte qu'elle renvoie un tuple comportant les mêmes Expression et str que précédemment ainsi qu'un dictionnaire qui associe à tous les token de type "variable" l'objet de type Variable associé.

La fonction ainsi créée aura donc comme signature

def read_expression(flot: str) -> (Expression, dict[str, Variable], str):
    pass

b. Affectez une valeur aux variables

Testez votre code en prenant le canevas ci-dessous :

flow = "3 + a"

(e, d, _) = read_expression(flow)

##
# Code à implémenter
##

print(f'{e} = {e.eval()}')

Et en implémentant une boucle qui va parcourir tous objets de type Variable dans d et leur affecte une valeur.

Évaluez votre code sur l'expression "a + a". Qu'observez-vous ?

c. Gérez les occurrences multiples d'une même variable

Modifiez la fonction read_expression() (une seconde fois) afin qu'elle prenne la signature suivante :

def read_expression(flot: str, dict[str, Variable] = None) -> (Expression, dict[str, Variable], str):
    pass

Modifiez ensuite la partie

        ...
        elif token[0].isalpha():
            currentExpression = Variable(token)
        ...

de telle sorte que, si le token est déjà présent dans le dictionnaire fourni en argument, on ne crée pas de nouvel objet de type Variable mais qu'on affecte à currentexpression la variable déjà présente dans le dictionnaire.

d. Validation

Validez votre code sur les exemples suivants :

a + 3
3 + a
a + b
a - a
a + 3 + a

Partie optionnelle : Gérer les parenthèses

Cette partie nécessite de maîtriser la notion de récursivité. Il est inutile d'aborder cette partie si le concept ne vous est pas familier.

Pour gérer les parenthèses correctement, il faut implémenter les étapes suivantes :

déclencher une nouvelle action lors de la lecture du token (. Cette action consiste en un appel de lecture d'expression (appel récursif). Au retour de cet appel récursif, le prochain token doit forcément être ) sinon on provoque une exception de type SyntaxError.
la subtilité réside dans la gestion des token ). Si on rencontre un ) en dehors du cas précédent -- lecture de ( suivi d'une Expression puis à nouveau un ) -- il faut s'assurer que l'expression courante est bien formée : previousExpression doit être différent de None notamment. Ensuite, il est important de remettre le token ) au début du flot de lecture, de sorte qu'il puisse être lu à la fin de l'appel récursif du point précédent.

Vous trouverez des tests unitaires pour la gestion des parenthèses ici.

Partie optionnelle : Gérer la priorité des opérateurs (difficile)

Faire en sorte que

flow1 = "2 + 3 * 4"
flow2 = "3 * 4 + 2"

s'évaluent en la même valeur 14.

Keys	Action
`?`	Open this help
`n`	Next page
`p`	Previous page
`s`	Search

TP - Évaluateur d'expressions

Introduction

Première partie : la classe Parser

1. Créer la classe Parser

2. Créer la méthode is_in_alphabet

3. Créer la méthode get_token