(* Programmieraufgabe P-48 (norm.ml)                                         *)
(* Leonhard Fellermayr                                                       *)

open Syntax

type seiten = Links | Rechts

let opSign o = match o with Plus -> "+" | Minus -> "-" | Mal -> "*";;

let string_of_expr e = let do_kl e = "(" ^ e ^ ")" in 
  let rec klammere e outerop s = match (e,outerop,s) with
      (Op(_,_,_),Plus,_)      -> soe e
    | (Op(_,_,_),Minus,Links) -> soe e
    | (Op(Mal,_,_),_,_)       -> soe e
    | (Op(o,l,r),_,_)         -> do_kl ((soe l) ^ (opSign o) ^ (soe r))
    | _                       -> soe e
  and soe = function
      Op(o,l,r) -> (klammere l o Links) ^ (opSign o) ^ (klammere r o Rechts)
    | Var x -> x
    | Num x -> if x >= 0 then string_of_int x else do_kl (string_of_int x)
  in soe e;;

(* isop : Pruefe, ob uebergebener Ausdruck eine Op[eration] ist
          Wird z. B. benoetigt, um festzustellen, ob weitere rekursive
          Aufrufe (fuer die "childs" der Operation) stattfinden muessen
          oder nicht... 
*)

let isop = function
  Op(_,_,_) -> true | _ -> false ;;

let isvar = function
  Var x -> true | _ -> false ;;

let isnum = function
  Num x -> true | _ -> false ;;

let rec normalise = function
      Var x -> Var x
    | Num x -> Num x
    | Op(Mal,Num a,Num b)   -> Num (a*b)
    | Op(Plus,Num a,Num b)  -> Num (a+b)
    | Op(Minus,Num a,Num b) -> Num (a-b)
    | Op(Plus,a,b) when a=b -> Op(Mal,Num 2,a)
    | Op(Plus,Op(Mal,Num x,Var y),Op(Mal,Num a,Var b)) when y=b -> normalise (Op(Mal,Num(x+a),Var y))
    | Op(Plus,Num x,Op(Plus,Num y,b)) -> Op(Plus,Num(x+y),b)
    | Op(Mal,Op(Mal,Num x,b),Num y) -> normalise (Op(Mal,b,Num (x*y)))
    | Op(Mal,Op(Plus,a,b),Op(Plus,c,d)) -> normalise(Op(Plus,normalise(Op(Plus,normalise(Op(Plus,normalise(Op(Mal,a,c)),normalise(Op(Mal,a,d)))),normalise(Op(Mal,b,c)))),normalise(Op(Mal,b,d))))
    | Op(Mal,Op(Minus,a,b),Op(Plus,c,d)) -> normalise (Op(Mal,Op(Plus,c,d),Op(Minus,a,b)))
    | Op(Mal,Op(Plus,a,b),Op(Minus,c,d)) -> normalise(Op(Minus,normalise(Op(Plus,normalise(Op(Minus,normalise(Op(Mal,a,c)),normalise(Op(Mal,a,d)))),normalise (Op(Mal,b,c)))),normalise(Op(Mal,b,d))))
    | Op(Mal,a,b) when ((isop a) && not (isop b)) || ((isvar a) && (isnum b)) -> normalise (Op (Mal,b,a))
    | Op(Plus,a,b) when (isop a) && not (isop b) || ((isvar a) && (isnum b)) -> normalise (Op (Plus,b,a))
    | Op(x,l,r) -> Op(x,(normalise l),(normalise r)) ;;

(* EOF *)