Reverse Polish Notation Evaluation

rpn.ml

exception RPN_eval

type token =
  | Num of float
  | Binary of (float -> float -> float)
  | Unary of (float -> float)

let eval_rpn tokens =
  let rec aux ~stack tokens =
    match tokens, stack with
    | [], [ result ] -> result
    | Num x :: tokens, stack -> aux ~stack:(x :: stack) tokens
    | Binary f :: tokens, b :: a :: stack -> aux ~stack:(f a b :: stack) tokens
    | Unary f :: tokens, a :: stack -> aux ~stack:(f a :: stack) tokens
    | _ -> raise RPN_eval
  in
  aux ~stack:[] tokens
;;

let () =
  print_float
    (eval_rpn
       [ Num 4.0
       ; Num 5.0
       ; Num 10.0
       ; Binary ( /. )
       ; Binary ( +. )
       ; Unary Float.floor
       ]);
  print_newline ()
;;