Task

Create a stack-based evaluator for an expression in   reverse Polish notation (RPN)   that also shows the changes in the stack as each individual token is processed as a table.



 Assume an input of a correct, space separated, string of tokens of an RPN expression
 Test with the RPN expression generated from the   Parsing/Shunting-yard algorithm   task: 

         3 4 2 * 1 5 - 2 3 ^ ^ / + 

 Print or display the output here


Notes

    ^    means exponentiation in the expression above.
    /    means division.


See also

   Parsing/Shunting-yard algorithm for a method of generating an RPN from an infix expression.
   Several solutions to 24 game/Solve make use of RPN evaluators (although tracing how they work is not a part of that task).
   Parsing/RPN to infix conversion.
   Arithmetic evaluation.


(* binop : ('a -> 'a -> 'a) -> 'a list -> 'a list *)
let binop op = function
  | b::a::r -> (op a b)::r
  | _ -> failwith "invalid expression"
 
(* interp : float list -> string -> string * float list *)
let interp s = function
  | "+" -> "add",    binop ( +. ) s
  | "-" -> "subtr",  binop ( -. ) s
  | "*" -> "mult",   binop ( *. ) s
  | "/" -> "divide", binop ( /. ) s
  | "^" -> "exp",    binop ( ** ) s
  | str -> "push", (float_of_string str) :: s
 
(* interp_and_show : float list -> string -> float list *)
let interp_and_show s inp =
  let op,s' = interp s inp in
  Printf.printf "%s\t%s\t" inp op;
  List.(iter (Printf.printf "%F ") (rev s'));
  print_newline ();
  s'
 
(* rpn_eval : string -> float list *)
let rpn_eval str =
  Printf.printf "Token\tAction\tStack\n";
  let ss = Str.(split (regexp_string " ") str) in
  List.fold_left interp_and_show [] ss