Consignes

Vous devrez soumettre votre travail (un unique fichier Caml valide) en utilisant l'interface TPLab.

Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :

  1. la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),
  2. la présence de commentaires aux endroits appropriés,
  3. ...

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

Liens utiles

1. expressions arithmétiques

Le but de cet exercice est d'écrire un petit ensemble de fonctions pour manipuler les expressions arithmétiques telles que 3+(4 * (2+3)) ou (a+b)*(a+b) - 2*a*b.

Donnez un type de données expr pour les expressions arithmétiques. Une expression arithmétique est :

La fonction print_int : int -> unit permet d'afficher un entier à l'écran. En utilisant cette fonction ainsi que les fonctions print_char et print_string ainsi que l'opérateur ; pour séquentialiser les commandes, écrivez une fonction print_expr : expr -> unit.

Par exemple, votre fonction pourra afficher la chaîne (7 * X1) + (0 * X2) pour l'expression correspondant à (7*X1) + (0*X2).

Écrivez une fonction calcule : expr -> int qui calcule la valeur entière d'une expression arithmétique sans variables.

Modifiez cette fonction pour qu'elle prenne un argument supplémentaire env censé contenir les valeurs des variables dans un dictionnaire (liste de couples). Vous pouvez utiliser la fonction List.assoc pour rechercher une valeur dans un dictionnaire.

Pouvez-vous facilement transformer votre fonction en fonction récursive terminale ?

Écrivez une fonction transforme : string -> expr qui transformera une chaîne de caractère utilisant la notation polonaise préfixée en expression arithmétique.

La notation polonaise préfixée fonctionne de la manière suivante : le symbole arithmétique (binaire) vient avant ses deux arguments. Par exemple, pour l'expression 3 + ((12 - X) * 2) on notera + 3 * - 12 X 2.

Les fonctions suivantes peuvent vous être utiles :

  • int_of_string : string -> int qui transforme une chaîne de caractères en entier.
  • Str.split : Str.regexp -> string -> string list qui permet de séparer une chaîne en morceaux, en utilisant une expression régulière.

    Pour utiliser Str.split, il faut soit lancer Caml avec ocaml str.cma, soit ajouter 

      #load "str.cma";;
    Pour découper une chaîne selon les espaces, vous pouvez utiliser: 

      # let split s = Str.split (Str.regexp_string " ") s;;
  val split : string -> string list = <fun>
  # split "Salut, je m'appelle Bob !";;
  - : string list = ["Salut,"; "je"; "m'appelle"; "Bob"; "!"]

Écrivez une fonction auxiliaire de type string list -> expr * string list qui renverra la première expression lue dans la liste, ainsi que la partie de la liste qui n'a pas servie pour créer l'expression : 

  aux ["+"; "*"; "12"; "X"; "Y"; "-"; "0"; "X"; ...]
  -->
  (Add(Mult(Val(12),Var("X")),Var("Y")) ,  ["-"; "0"; "X"; ...])

Pour tester, la fonction read_line qui lit une chaîne de caractères sur l'entrée standard pourra vous servir...

2. comparaison d'expression arithmétiques

Comment pouvez tester l'équivalence de deux expressions arithmétiques sans variable ? Écrivez la fonction correspondante equiv_sans_var : expr -> expr -> bool.

À votre avis, comment peut-on tester l'équivalence de deux expressions arithmétiques avec des variables. (Pas la peine de le faire, donnez simplement des idées.)

Un polynôme à coefficients entiers et à plusieurs variables peut être représenté par 

type monome = int * (string list)
type polynome = monome list

Par exemple, le polynôme X1 2 + 2X1 X2 + X2 2 est représenté par [(1, ["X1"; "X1"]); (2, ["X1"; "X2"]); (1, ["X2"; "X2"])]

Écrivez une fonction normalize : expr -> polynome qui développe une expression arithmétique pour la transformer en polynôme correspondant.

Pour ceci, il sera intéressant d'écrire les fonctions

Essayez de faire en sorte que deux expressions arithmétiques équivalentes (comme (X1+X2)*(X1+X2) et X1*X1 + 2*X1*X2 + X2*X2) soient normalisées en polynômes égaux.