I'm studying for the course of "Programming Paradigm" (traslation of Paradigmi di Programmazione) where we study different programming approaches by using some new programming languages.

The first programming language we are using is ocaml, a functional programming oriented language (for more informations read the ocaml Wikipedia page).

As first exercise we have developed a simple math expression calculator: for example given a string like (3*2)+5 the program is able to calculate the result.

This is the grammar used for the evaluation:

expr = plus_expr | plus_expr + expr
  plus_expr = mul_expr | mul_expr * plus_expr
  mul_expr = number | ( expr )

Even if it looks like a simple exercise it was actually not so easy.. my first steps into a functional programming language were quite difficult as really different from an imperative programmer point of view.

Actually the first two days using ocaml where a nightmare.. everything looked absolutely difficult. Fortunately I had the idea to ask for some help on #ocaml on irc.freenode.net.

The guys there where wonderful with me really helping me moving my first steps with this language. Especially I would like to tank Goswin von Brederlow (mrvn on #ocaml) who really helped me with my problems. He has been so kind that he developed for me 4 solutions to the problem using different approaches.

I present here Goswin's and mine solutions:

1. recursive functions on a char list
2. recursive functions on a string
3. uses a single "compute" function with an option type (num) and bool (plus) to track the state it is in and recursion to calculate the result
4. converts the input to polish notation (uses the Shunting yard algorithm)
5. my solution based on recursive functions on a string

The fourth approach is probably the better because it is tail recursive then is able to handle arbitrarily complex expressions while the other implementations are limited by the recursion depth.

There is also a downloadable archive containing all the 5 implementations.

recursive functions on a char list

(* simple calculator: Copyright Goswin von Brederlow 
 
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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 
*)
 
let explode s =
  let rec loop acc = function
      0 -> s.[0] :: acc
    | x -> loop (s.[x] :: acc) (x - 1)
  in
    loop [] (String.length s - 1)
 
let rec implode = function
    [] -> ""
  | x::xs -> (String.make 1 x) ^ (implode xs)
 
let is_digit x = (x >= '0') && (x <= '9')
let int_of_digit x = (int_of_char x) - (int_of_char '0')
 
(*
  expr = plus_expr | plus_expr + expr
  plus_expr = mul_expr | mul_expr * plus_expr
  mul_expr = number | ( expr )
*)
 
exception Error of char list
 
let number l =
  let rec loop acc = function
      x::xs when is_digit x -> loop (10 * acc + (int_of_digit x)) xs
    | l -> (acc, l)
  in
    loop 0 l
 
let rec mul_expr l = match l with
    x::xs when is_digit x -> number l
  | '('::xs -> begin
      let (x, l) = expr xs
      in
        match l with
            ')'::xs -> (x, xs)
          | _ -> raise (Error(l))
    end
  | _ -> raise (Error(l))
and plus_expr l =
  let (x, l) = mul_expr l
  in 
    match l with
        '*'::xs ->
          let (y, l) = plus_expr xs
          in
            (x * y, l)
      | _ -> (x, l)
and expr l =
  let (x, l) = plus_expr l
  in 
    match l with
        '+'::xs ->
          let (y, l) = expr xs
          in
            (x + y, l)
      | _ -> (x, l)
 
let calc s =
  Printf.printf "%s = " s;
  try
    let l = explode s in
    let (x, l) = expr l
    in
      match l with
          [] -> Printf.printf "%d\n" x
        | _ -> raise (Error(l))
  with Error(l) -> Printf.printf "Parse error at '%s'\n" (implode l)
 
let _ =
  List.iter calc ["1"; "1+1"; "2*3"; "(1)"; "1+2*3"; "2*(3+4)*5"; "2+3*4(5)"]

recursive functions on a string

(* simple calculator: Copyright Goswin von Brederlow 
 
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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 
*)
 
(*
  expr = plus_expr | plus_expr + expr
  plus_expr = mul_expr | mul_expr * plus_expr
  mul_expr = number | ( expr )
*)
 
exception Error of string * int
 
let calc s =
  let len = String.length s in
  let is_digit pos = (s.[pos] >= '0') && (s.[pos] <= '9') in
  let int_of_digit pos = (int_of_char s.[pos]) - (int_of_char '0') in
  let number pos =
    let rec loop acc pos =
      if (pos >= len) || (not (is_digit pos))
      then (acc, pos)
      else loop (10 * acc + (int_of_digit pos)) (pos + 1)
    in
      loop 0 pos
  in
  let rec mul_expr pos =
    if is_digit pos
    then number pos
    else if s.[pos] = '('
    then
      let (x, pos) = expr (pos + 1)
      in
        if s.[pos] = ')'
        then (x, pos + 1)
        else raise (Error ("mul_expr", pos))
    else raise (Error ("mul_expr2", pos))
  and plus_expr pos =
    let (x, pos) = mul_expr pos
    in
      if (pos >= len) || (s.[pos] <> '*')
      then (x, pos)
      else
        let (y, pos) = plus_expr (pos + 1)
        in
          (x * y, pos)
  and expr pos =
    let (x, pos) = plus_expr pos
    in 
      if (pos >= len) || (s.[pos] <> '+')
      then (x, pos)
      else
        let (y, pos) = expr (pos + 1)
        in
          (x + y, pos)
  in
    Printf.printf "%s = " s;
    try
      let (x, pos) = expr 0
      in
        if pos >= len
        then Printf.printf "%d\n" x
        else raise (Error ("calc", pos))
    with Error(name, pos) ->
      let marker = String.make (pos + 1) '-'
      in
        marker.[pos] <- '^';
        Printf.printf "Parse error in %s at %d:\n" name pos;
        Printf.printf "%s\n" s;
        Printf.printf "%s\n" marker
 
let _ =
  List.iter calc ["1"; "1+1"; "2*3"; "(1)"; "1+2*3"; "2*(3+4)*5"; "2+3*4(5)"]

single "compute" function

(* simple calculator: Copyright Goswin von Brederlow 
 
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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 
*)
 
let explode s =
  Array.to_list (Array.init (String.length s) (fun i -> s.[i]))
 
let rec implode = function
    [] -> ""
  | x::xs -> (String.make 1 x) ^ (implode xs)
 
let some = function Some x -> x | None -> raise (Invalid_argument "some")
let is_digit x = (x >= '0') && (x <= '9')
let int_of_digit x = (int_of_char x) - (int_of_char '0')
 
let rec parse_number acc = function
    x::xs when is_digit x -> parse_number (10 * acc + (int_of_digit x)) xs
  | l -> (acc, l)
 
exception Error of string * char list
 
let rec compute num plus l = match (l, num, plus) with
    ([], Some x, _) -> (num, [])
  | (x::xs, None, _) when is_digit x ->
      let (x, l) = parse_number 0 l
      in
        compute (Some x) plus xs
  | ('+'::xs, Some x, true) ->
      let (num, l) = compute None true xs
      in
        (Some (x + some num), l)
  | ('+'::xs, Some x, false) -> (num, l)
  | ('*'::xs, Some x, _) ->
      let (num, l) = compute None false xs
      in
        compute (Some (x * some num)) true l
  | ('('::xs, None, _) ->
      let (num, l) = compute None true xs
      in begin
          match l with
              ')'::xs -> (num, xs)
            | _ -> raise (Error ("OPEN", l))
        end
  | (')'::xs, Some x, _) -> (num, l)
  | _ -> raise (Error ("compute", l))
 
let calc s =
  Printf.printf "%s = " s;
  try
    let l = explode s in
    let (x, _) = compute None true l in
      Printf.printf "%d\n" (some x);
  with
      Error(name, l) ->
        Printf.printf "Error in %s at '%s'\n" name (implode l)
 
let _ =
  List.iter calc ["1"; "1+1"; "2*3"; "(1)"; "1+2*3"; "2*(3+4)*5";
                  "2+3*4(5)"; "2++2"; "2+3+c"; "1++"; "+1"]

converts the input to polish notation creating a tail recursion

(* simple calculator: Copyright Goswin von Brederlow 

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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */

*)

let explode s = Array.to_list (Array.init (String.length s) (fun i -> s.[i]))
let is_digit x = (x >= '0') && (x <= '9')
let int_of_digit x = (int_of_char x) - (int_of_char '0')

type item = Num of int | Op of char

let apply l op = match (l, op) with
    (x::y::l, Op '+') -> (x+y)::l
  | (x::y::l, Op '*') -> (x*y)::l
  | (l, Num x) -> x::l
  | _ -> raise (Invalid_argument "Unknown operator or missing argument.")

let rec conv (acc:int list) stack l = match (l, stack) with
    ([], []) ->
      (match acc with x::[] -> x | _ -> raise (Invalid_argument "Extra numbers on stack."))
  | ([], (_, x)::xs) -> conv (apply acc x) xs []
  | (x::xs, (_, Num n)::ns) when is_digit x ->
      conv acc ((0, Num (n*10+(int_of_digit x)))::ns) xs
  | (x::xs, _) when is_digit x ->
      conv acc ((0, Num (int_of_digit x))::stack) xs
  | ('+'::xs, (pre, x)::ns) when pre < 2 -> conv (apply acc x) ns l
  | ('+'::xs, _) -> conv acc ((2, Op '+')::stack) xs
  | ('*'::xs, (pre, x)::ns) when pre < 1 -> conv (apply acc x) ns l
  | ('*'::xs, _) -> conv acc ((1, Op '*')::stack) xs
  | ('('::xs, _) -> conv acc ((3, Op '(')::stack) xs
  | (')'::xs, (_, Op '(')::ns) -> conv acc ns xs
  | (')'::xs, (_, x)::ns) -> conv (apply acc x) ns l
  | _ -> raise (Invalid_argument "Parse error.")

let calc s =
  try
    let l = explode s in
    let x = conv [] [] l
    in
      Printf.printf "%s = %d\n" s x
  with Invalid_argument e -> Printf.printf "%s: %s\n" s e

let _ =
  List.iter calc ["1"; "1+1"; "2*3"; "(1)"; "1+2*3"; "2*(3+4)*5";
          "2+3*4(5)"; "2++2"; "2+3+c"; "1++"; "+1"]

my implementation

(*
 * Parser di Espressioni Matematiche
 * Created by Fabio Varesano - 2007/05/04 
 
 Valori int_of_char
 ( 40
 ) 41
 * 42
 + 43


let explode s =
  let rec loop acc = function 0 -> s.[0] :: acc | x -> loop (s.[x] :: acc) (x - 1)
  in loop [] (String.length s - 1);;

explode "2*3";;
 *)


let is_numeric x = (x >= '0') && (x <= '9');;

let int_of_digit c = (int_of_char c) - (int_of_char '0');;

let calc s =
  let rec f f_pivot =
(*     Printf.printf "f %d = " f_pivot; *)
    if ( is_numeric s.[f_pivot] ) then
      begin
(*       Printf.printf "%d\n" (int_of_digit s.[f_pivot]); *)
      (int_of_digit s.[f_pivot], f_pivot + 1)
      end
    else if (s.[f_pivot] = '(') then
      let (value, pos) = e (f_pivot+1) in 
        if(s.[pos] = ')') then
          (value, pos+1)
        else
          raise (Sys_error("f: invalid character: "^String.make 1 s.[f_pivot]))
    else
      raise (Sys_error("f: invalid character: "^String.make 1 s.[f_pivot]))
  and t t_pivot =
    let (f_value, f_pivot) = f t_pivot in
      if ( s.[f_pivot] = '*' ) then
        let (t_value, t_cpivot) = t (f_pivot+1) in
(*           Printf.printf "t %d = %d\n" t_pivot (f_value * t_value); *)
          ((f_value * t_value), t_cpivot)
      else
        (f_value, f_pivot)
(*         raise (Sys_error("t: invalid character: "^String.make 1 s.[f_pivot]^" value: "^string_of_int f_value)) *)
  and e e_pivot =
    let (t_value, t_pivot) = t e_pivot in
      if ( s.[t_pivot] = '+' ) then
        let (e_value, e_cpivot) = e (t_pivot+1) in
          ((t_value + e_value), e_cpivot)
      else
        (t_value, t_pivot)
(*         raise (Sys_error("e: invalid character: "^String.make 1 s.[t_pivot]^" value: "^string_of_int t_value)) *)

  in 
    Printf.printf "%s = " s;
    try
      Printf.printf "%d\n" (fst(e 0))
    with
      Sys_error(mess) -> Printf.printf "\n%s\n" mess;;


List.iter calc ["1#"; "1+1#"; "2*3#"; "(1)#"; "3*2*3#"; "1+2*3#"; "2*(3+4)*5#";
                  "2+3*4(5)#"; "2++2#"; "2+3+c#"; "1++#"; "+1#"; "2+((1))#"; "2+(1*(2)#"];;