Prépa Code Connexion Inscription

On représente une expression arithmétique par un arbre binaire strict : chaque nœud est soit une feuille contenant un entier, soit un nœud interne contenant un opérateur et exactement deux fils (opérande gauche, opérande droit).

type expr = F of int | N of string * expr * expr

Les opérateurs autorisés sont "+", "-" et "*". On suppose l'expression bien formée.

Écrire une fonction eval : expr -> int qui renvoie la valeur de l'expression.

Par exemple, l'expression (3 + 4) * 2 se représente par :

N("*", N("+", F 3, F 4), F 2)

et son évaluation vaut 14.