Source

spoj-ocaml / 00010.CMEXPR / cmexpr.ml

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


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_t (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

  in fst (parse_t 0)

let print tree =
  let op_prio = function
      '+' | '-' -> 1
    | _         -> 2
  in
  let op_assoc = function
      '+' | '*' -> true
    | _         -> false
  in

  let need_par op prio assoc is_left =
    let prio' = op_prio op in
    prio' < prio || (prio' == prio && not assoc && not is_left)
  in

  let rec print_aux prio assoc left = function
      Node (op, l, r) ->
        let npar = need_par op prio assoc left in
        if npar then print_char '(' ;
        print_aux (op_prio op) (op_assoc op) true l ;
        print_char op ;
        print_aux (op_prio op) (op_assoc op) false r ;
        if npar then print_char ')'
    | Leaf letter ->
        print_char letter
  in print_aux 0 true true 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.