DouKaku?

type token = Int of int | Mul | Div | Add | Sub

let add (a1, b1) (a2, b2) = (a1 * b2 + a2 * b1), (b1 * b2)
let sub (a1, b1) (a2, b2) = (a1 * b2 - a2 * b1), (b1 * b2)
let mul (a1, b1) n        = (a1 * n), b1
let div (a1, b1) n        = a1, (b1 * n)

let factor list =
  let rec factor' n = function
    | Int x :: tl -> factor' (n * 10 + x) tl
    | x           -> n, x in
  factor' 0 list

let term input =
  let rec term' (f,input)  = match input with
    | Mul :: tl -> let f2, tl2 = factor tl in term' ((mul f f2), tl2)
    | Div :: tl -> let f2, tl2 = factor tl in term' ((div f f2), tl2)
    | x         -> f, x in
  let n, input = factor input in term' ((n,1), input)

let expr input =
  let rec expr' (f,input) = match input with
    | Add :: tl -> let f2, tl2 = term tl in expr' ((add f f2), tl2)
    | Sub :: tl -> let f2, tl2 = term tl in expr' ((sub f f2), tl2)
    | _         -> f in
  expr' (term input)

let op = [| Add; Sub; Mul; Div |]

let rec makeexpr list o n =
  if n = 0 then list else match (o mod 5) with
    | 4 -> makeexpr (Int n           :: list) (o / 5) (n - 1)
    | x -> makeexpr (Int n :: op.(x) :: list) (o / 5) (n - 1)

let rec makestr s = function
  | []       -> s
  | hd :: tl -> makestr (s ^ (match hd with
    | Int x -> string_of_int x | Mul->"*" | Div->"/" | Add->"+" | Sub->"-")) tl

let rec main n = if n >= 0 then
    let ex = makeexpr [ Int 9 ] n 8 in
    let a, b = expr ex in
    let _ = if b * 100 = a then Printf.printf "%s\n" (makestr "" ex) in
    main (n - 1)

let _ = main 390624