Énoncé

Étant donné une formule de logique contenant uniquement les opérateurs "ou", "et" et "non", et des propriétés \(p_1\) jusqu'à \(p_{40}\), vous devez dire s'il existe un jeu de valeurs pour les propriétés tel que la formule est vraie. Par exemple, la formule "\(p_1\) et \(p_2\)" est vraie pour \(p_1\) vraie et \(p_2\) vraie. La formule "\(p_1\) et (non \(p_1\))" est par contre toujours fausse.

Entrée

L'entrée du programme contient la version pré-fixée de la formule de logique.
Soyons plus clairs : chaque ligne est soit un entier entre 1 et 40, représentant \(p_1\) jusqu'à \(p_{40}\), soit un opérateur ("et", "ou" ou "non"). Le tout est suivi d'un retour à la ligne. Pour retrouver la formule, on procède comme suit : si on lit un opérateur, on l'applique aux deux prochains (ou au prochain si c'est un "non") éléments "complets" qu'on lira, si c'est un entier i, on considère l'élément pi qui lui correspond.
Par exemple: la formule "\(p_1\) et ((non \(p_2\)) ou (non \(p_1\)))" pourra être représentée par:

et
1
ou
non
2
non
1

Ce qui se lit: "Je fais d'abord un "et". Le premier élément du "et" est \(p_1\). Le second est un "ou". Ce "ou" a pour premier élément une négation. C'est la négation de \(p_2\). Il a pour second élément une négation. C'est la négation de \(p_1\)." : son écriture infixe est donc "\(p_1\) et ((non \(p_2\)) ou (non \(p_1\)))".
La formule sera toujours bien formée.

Sortie

La sortie de votre programme doit indiquer "true" si la formule de l'entrée peut être rendue vraie et "false" sinon. La réponse devra être suivie d'un retour à la ligne.

Exemples

Entrée	Sortie
et 1 ou non 2 non 1	true
et 1 ou non 1 non 1	false
et 5 non ou et 1 2 et 3 4	true
et non et et et et 14 26 et 21 36 et et 22 22 et 19 11 et ou et 18 21 non 14 et et 39 35 non 1 et et et et 14 26 et 21 36 et et 22 22 et 19 11 et ou et 18 21 non 14 et et 39 35 non 1	false

Squelette CamlLight et OCaml

(* Ce fichier contient tout ce qu'il faut pour lire les donnees en entree, les 
mettre dans des variables, et afficher votre resultat final en sortie. *)

(* Fonction pour lire l'entree et la representer dans le format de votre choix --- a completer --- *)
let rec lit_entree () = 
  let ligne = input_line stdin in
  if ligne <> "" then
  begin
    let i = 
      try int_of_string ligne with _ -> 0
    in
    if i = 0
    then 
      (* dans ce cas, ligne est un operateur, soit "non", "et" ou "ou" *)
    else
      (* dans ce cas, i est le numero de la propriete consideree (pi) *)
    ;
    lit_entree ();
  end
;;

lit_entree ();;

(* fonction pour afficher votre solution *)
let affiche_solution b =
  if b then print_string "true" else print_string "false";
  print_newline();;

(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)

(* Debut de votre programme *)


(* Fin de votre programme *)