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 ()
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.