1. Vadim Shender
  2. spoj-ocaml

Source

spoj-ocaml / 00004.ONP / onp.ml

(* https://www.spoj.pl/problems/ONP/ *)


let id x = x
let (|>) x y = y x


type tree =
  Leaf of char
| Node of char * tree * tree

let parse expr =
  let len = String.length expr in

  let rec parse_a i =
    match expr.[i] with
      '('    ->
        let tree, i = parse_d (i + 1) in
        tree, i + 1
    | letter ->
        Leaf letter, i + 1

  and parse_m' left i =
    if i < len && (expr.[i] == '*' || expr.[i] == '/') then
      let right, i' = parse_a (i + 1) in
      parse_m' (Node (expr.[i], left, right)) i'
    else
      left, i
  and parse_m i = let left, i = parse_a i in parse_m' left i

  and parse_t' left i =
    if i < len && (expr.[i] == '+' || expr.[i] == '-') then
      let right, i' = parse_m (i + 1) in
      parse_t' (Node (expr.[i], left, right)) i'
    else
      left, i
  and parse_t i = let left, i = parse_m i in parse_t' left i

  and parse_d' left i =
    if i < len && expr.[i] == '^' then
      let right, i' = parse_t (i + 1) in
      parse_d' (Node (expr.[i], left, right)) i'
    else
      left, i
  and parse_d i = let left, i = parse_t i in parse_d' left i

  in fst (parse_d 0)

let print tree =
  let rec print_aux = function
      Node (op, l, r) -> print_aux l; print_aux r; print_char op
    | Leaf letter     -> print_char letter
  in print_aux tree; print_newline ()


let main () =
  let t = Scanf.scanf "%d\n" id in
  for i = 1 to t do
    let expr = Scanf.scanf "%s\n" id in
    expr |> parse |> print
  done

let () = main ()