Tâche «Transformation d’un arbre d’expressions à l’aide d’enum et de pattern matching»

Soit une expression arithmétique représentée sous forme d’un arbre binaire. Chaque nœud de l’arbre est soit un nombre (feuille), soit une opération (addition, soustraction, multiplication, division) avec deux descendants. Il faut implémenter une fonction qui prend un tel arbre et retourne un nouvel arbre simplifié selon les règles suivantes : si un nœud est une opération et que ses deux descendants sont des nombres, calculer le résultat et remplacer le nœud par un nombre ; si l’un des descendants est le nombre 0 et que l’opération est une multiplication, remplacer le nœud par 0 ; si l’un des descendants est le nombre 0 et que l’opération est une addition, remplacer le nœud par l’autre descendant ; si l’opération est une division et que le diviseur est le nombre 1, remplacer le nœud par le dividende ; si l’opération est une soustraction et que les deux descendants sont égaux, remplacer le nœud par le nombre 0. Appliquer récursivement tant que possible. Il est garanti que toutes les opérations sont entières, la division est entière avec arrondi vers le bas. Entrée : d’abord un entier n — le nombre de nœuds. Ensuite n lignes, chacune au format : type de nœud ("num" ou "op"), pour "num" — valeur (entière), pour "op" — symbole de l’opération ('+', '-', '*', '/') et deux entiers — indices du descendant gauche et du descendant droit (indexation 0). La racine a toujours l’indice 0. Sortie : pour chaque nœud après simplification, afficher son type et sa valeur/opération dans le même format (l’ordre des nœuds est celui de l’arbre d’origine, même si un nœud devient un nombre, conserver son indice). Si un nœud devient un nombre, afficher "num valeur" ; s’il reste une opération, afficher "op symbole gauche droite" (indices des descendants — de l’arbre simplifié).

Exemple 1

Exemple 2

Exemple 3

Exemple 4