(*
Copyright 2007 Jesse H-K

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*)

(*
 * An interactive calculator.
 * Only works with integers.
 * Includes division, multiplication, addition, and subtraction.
 * No operator precedence is currently implemented (and there are no brackets).
 *)


(* First, strip the input string of whitespace. *)
let strip_whitespace =
    let whitespace = Str.regexp "[ \n\t]*" in
    Str.global_replace whitespace ""
    
exception Invalid_token of string
exception Unexpected_token of string

(* Define all acceptable tokens in the expression. *)
type token =
    | Numb of int
    | Op of (int -> int -> int)
    | Begin (* A bit of a hack *)
    
(* Simply define the possible operations *)
let add = ( + ) 
let subtract = ( - )
let multiply = ( * )
let divide = ( / )
    
let int_of_char = function
    | '0' -> 0
    | '1' -> 1
    | '2' -> 2
    | '3' -> 3
    | '4' -> 4
    | '5' -> 5
    | '6' -> 6
    | '7' -> 7
    | '8' -> 8
    | '9' -> 9
    | ch -> failwith (Printf.sprintf "Can't convert char to int: \'%c\'" ch)
    
let token_of_char = function
    | '+' -> Op add
    | '-' -> Op subtract
    | '*' -> Op multiply
    | '/' -> Op divide
    | ch ->
        try
            Numb (int_of_char ch) 
        with _ -> raise (Invalid_token (Printf.sprintf "%c" ch))
        
let is_operand = function
    | Op _ -> true
    | _ -> false

let is_number = function
    | Numb _ -> true
    | _ -> false

let unexpected_operand ch = raise (Unexpected_token (Printf.sprintf "%c" ch))

(* Determines if a string begins with a number *)    
let is_number_string string =
    let number = Str.regexp "^[-+]?[0-9]+" in
    Str.string_match number string 0
    
(* Returns the string following a number in the string. *)
let string_after_number string =
    if not (is_number_string string) then failwith "Unable to convert string to number."
    else Str.string_after string (Str.match_end () )

(* Return a token list from a string. *)
let tokenize string =
    let raw = strip_whitespace string in
    
    (*
     A tail-recursive function.
       
     "result" is the accumulated list of tokens.
     "expr" is the expression remaining to tokenize.
     "prev" is the previous token parsed.
     *)
    let rec tr_tokenize result expr prev =
        (* On an empty remainder, return the result *)
        if expr = "" then result
        else (
            let char = expr.[0] in
            if (is_operand prev) && (is_operand (token_of_char char)) then unexpected_operand char
            else (
                (* If the first char of the expression is a digit, look for a number *)
                if is_number (token_of_char char) then
                    let rest = string_after_number expr in
                    let numb = Numb (int_of_string (Str.matched_string expr)) in
                    
                    (* Add the number to the token list, and tokenize the rest of the expression. *)
                    tr_tokenize (result @ [numb]) rest numb
                else (
                    (* It's not a digit, so it must be a operand. Error handling covered in token_of_char *)
                    let op = token_of_char char in
                    let rest = Str.string_after expr 1 in
                    
                    tr_tokenize (result @ [op]) rest op)))
    in
    
    tr_tokenize [] raw Begin

(* Given an Op, and two Numbs, return the result *)
let apply_operation op a b = match (op, a, b) with
    | (Op operand, Numb x, Numb y) -> operand x y
    | _ -> failwith "apply_operation"
    
exception Invalid_expression of string

(* Evaluate mathematical expressions. *)
let evaluate string =
    let token_list = tokenize string in
    
    let rec tr_evaluate result tlist = match tlist with
        | op :: b :: xs -> tr_evaluate (apply_operation op (Numb result) b) xs
        | [] -> result
        | _ -> raise (Invalid_expression string)
    in
    
    match token_list with
        (* A normal expression beginning with a number *)
        | (Numb n) :: xs -> tr_evaluate n xs
        
        (* Handles expressions like "-3 + 4". ie, expressions that begin with an operator *)
        | (Op op) :: (Numb a) :: xs -> tr_evaluate (op 0 a) xs
        
        (* Given an empty list, the answer is 0 *)
        | [] -> 0
        
        (* Anything else is an invalid expression *)
        | _ -> raise (Invalid_expression string)
        
let main_loop () = 
    while true do
        print_string ">> ";
        let input = read_line () in
        
        try
            print_int (evaluate input);
            print_newline ();
        with error -> print_endline (Printexc.to_string error);
   done
  
let _ = main_loop ()

$ ocamlfind opt -package str -linkpkg parse.ml -o parse

$ ./parse
>> 2 + 3
5
>> 10 + 30
40
>> -10 - 30
-40
>> -10 - 
Parse.Invalid_expression("-10 - ")
>> 10 +-
Parse.Unexpected_token("-")
>> 3 + a
Parse.Invalid_token("a")
>> 3 + 2
5
>> 45 * 100
4500
>> 45 * 100 + 2
4502
>> 100 / 3
33
>> 50 / 2
25
>> 50 / 2 / 3
8
>> 100 + 2 - 4 + 8 * 50 / 10
530
>> Fatal error: exception End_of_file

CamlCalc version 0.1, Copyright (C) 2007 Jesse H-K
CamlCalc comes with ABSOLUTELY NO WARRANTY.
>> 2 + 3
5
>> 42 - 4 * 3
30
>> 108 * 11 - 4
1184
>> -3 - -2 
-1
>> -3 * -3
9
>> 100^3
1000000
>> 321^123
199580904170858944588683464608694075062943107082809027605498347841561605181074274426665986623764972439807786764739130193391688887305693295698132008415537889753720415793877902074665765736230030622222862498385818118244547668141388643750880896837470534556730014314212951333550122949806119583030226121714710874561
>> 48/50 + 1/2
73/50
>> Fatal error: exception End_of_file