open Printf
open Scanf

type tree = L of int | T of tree * char * tree
 
(* 
   E ::= T E1
   E1 ::= _ | + T E1 | - T E1
   T ::= F T1
   T1 ::= _ | * F T1 | / F T1
   F ::= num | ( E )
*)

(* "%0c" obtine caracterul fara sa-l consume; "%_c" citeste si ignora *)
let rec expr() =
  let factor () = 
    try scanf " %0c" (function
    | '(' -> scanf "%_c" ();
      let e = expr() in (
        try scanf " )" (); e
        with Scan_failure _ | End_of_file -> failwith "missing )"
      )
    | _ -> scanf " %d" (fun n -> L n))
    with Scan_failure _ | End_of_file -> failwith "number or ( expected"
  in let term() =
       let rec term1 t =
         try scanf " %0c" (function 
         | '*' | '/' as c -> scanf "%_c" (); term1(T(t, c, factor())))
         with Match_failure _ | End_of_file -> t
  in term1 (factor())
     in let rec expr1 e =
          try    scanf " %0c" (function 
          | '+' | '-' as c -> scanf "%_c" (); expr1(T(e, c, term())))
          with Match_failure _ | End_of_file -> e
        in expr1 (term())

let rec preorder = function 
  | L n -> print_int n; print_char ' '
  | T (l, op, r) -> print_char op; print_char ' '; preorder l; preorder r

let rec inorder = function 
  | L n -> print_int n;
  | T (l, op, r) -> print_char '('; inorder l; printf " %c " op; inorder r; print_char ')'

let rec postorder = function 
  | L n -> print_int n; print_char ' '
  | T (l, op, r) -> postorder l; postorder r; print_char op; print_char ' '

let drawtree t =                (* deseneaza arbore *)
  let rec drawt1 rcnt = function (* rcnt = radacina; ret. urmatorul nr liber *)
    | L nval -> printf "%d [label=\"%d\"];\n" rcnt nval; rcnt + 1
    | T (l, op, r) ->
      let drawsub scnt subt = (* deseneaza subarbore si legatura de la rcnt *)
        printf "%d -> %d;\n" rcnt scnt; drawt1 scnt subt
      in printf "%d [label=\"%c\"];\n" rcnt op;
         drawsub (drawsub (rcnt+1) l) r (* r incepe de la nr. liber dupa l *)
  in ignore (drawt1 0 t)                (* numara de la zero *)

(* compilare: ocamlc exptree.ml                rulare: ./a.out > fisier.dot
 * afisare: dotty fisier.dot   sau PDF: dot -Tpdf fisier.dot -o fisier.pdf *)

let _ = print_endline "digraph g {"; drawtree (expr()); print_endline "}"

This document was generated using caml2html