Kursliste Logg inn

Informasjon

Frist 15/04/2026 23:00:00
Innleveringsgrense Ingen begrensning

Logg inn

Logg inn

Simplify

Dans cette partie du projet, vous pouvez utiliser la fonction evaluate qui est importée pour vous dans l'environnement. Les fonctions serialize et unserialize ne sont pas disponibles.

Votre tâche est d'implémenter la fonction simplify qui construit un nouvel arbre simplifié à partir d'un arbre original qui ne peut pas être modifié.

En plus de la simplification déjà présentée et reprise dans la post-condition de cette fonction, un ensemble d'autres opérations de simplification (fort utiles pour la dernière partie de ce projet) doivent être implémentées dans cette fonction. Par exemple, toute multiplication par 0 vaut 0 quelque soit l'autre opérande de la multplication. Cela veut dire qu'un arbre correspondant à l'expression parenthésée (x * 0.0) peut être simplifié en un arbre équivalent réduit à la feuille 0.0. La même propriété s'applique pour (0.0 * x) mais aussi si, au lieu de x, on a une valeur numérique, une autre variable ou tout un (sous-)arbre.
La règle de simplification générale est donc que (T * 0.0) == (0.0 * T) == 0.0 pour tout (sous-)arbre T.

Plus généralement, la table suivante résume toutes les opérations de simplification complémentaires à implémenter pour un arbre (et par récursion, pour ses sous-arbres).

https://inginious.info.ucl.ac.be/course/LINFO1103/projet-3/simplify.jpg

Trucs et astuces

  • Pensez aux cas de base.
  • Pour pouvoir simplifier un arbre, il est particulièrement pertinent que ses sous-arbres soient déjà simplifiés. Cette propriété doit vous guider dans la manière d'organiser la récursion.
  • La signature de la fonction impose que la valeur renvoyée soit toujours un arbre. Si la simplification vous conduit à une valeur numérique pour l'ensemble de l'arbre, l'arbre simplifié doit être réduit à une feuille contenant cette valeur numérique.
  • La post-condition de la fonction doit être vérifiée en plus des règles complémentaires de simplification reprises dans la table ci-dessus.
  • Bien que les règles de simplification soient présentées dans la table de façon synthétique via des expressions parenthésées, la fonction simplify prend comme premier argument un arbre tree. Il ne s'agit donc pas d'implémenter ces simplications sur des chaînes de caractères représentant un arbre mais bien directement sur une structure de données de type Tree. C'est la raison pour laquelle les fonctions serialize et unserialize ne peuvent pas être utilisées. L'arbre original passé en paramètre ne doit pas être modifié mais un nouvel arbre doit être créé et renvoyé.

Veuillez soumettre le corps de la fonction suivante:

def simplify(tree: Tree, digits:int = -1) -> Tree:
    """
    :pre: tree est un arbre syntaxique valide
    :return: un arbre syntaxique valide, équivalent au premier
    :post: l'arbre renvoyé (et ses sous-arbres, par récursion) est soit réduit à une feuille,
        soit contient un opérateur à sa racine, qui a dans sa descendance au moins une variable.
        l'arbre original passé en paramètre n'est *pas* modifié, un nouvel arbre (simplifié) est renvoyé.
        Les valeurs numériques dans l'arbre simplifié sont arrondies à 'digits' décimales,
        sauf si 'digits' est négatif (le cas par défaut).
    """
    # vous aurez probablement besoin de la fonction evaluate :-)