F# How to parse and evaluate calculator expressions with string input

Question

I have to create a calculator in F#, and im stuck on a task.

I need to pass a sum in as a string into the console e.g. "4 + 5" and parse and calculate it.

any ideas?

any help would be greatly appreciated

open System

let rec calculator() =
    printf "Choose a sum type \n1: Addition\n2: Subtraction\n3: Mulitiplication\n4: Division\n\n\n"

    let input = Console.ReadLine();

    printf "now type in 2 numbers\n"

    let num1 = Console.ReadLine();
    let num2 = Console.ReadLine();

    let a : int = int32 num1
    let b : int = int32 num2

    let addition x y = x + y
    let subtraction x y = x - y
    let multiply x y = x * y
    let divide x y = x / y 

    match input with

    | "1" -> printfn("The result is: %d")(addition a b)
    | "2" -> printfn("The result is: %d")(subtraction a b)
    | "3" -> printfn("The result is: %d")(multiply a b)
    | "4" -> printfn("The result is: %d")(divide a b)

    ignore(Console.ReadKey())
    ignore(calculator())

calculator()

Answer 1

Parsing expressions like 4 + 5 in a robust way usually involves relying on good tools like FsLex/FsYacc or FParsec.

Seasoned developers that like do things from scratch (not always a good thing) might implement something called a Recursive-Decent-Parser.

Others found all their parsing needs to be answered by RegEx. RegEx is however limited in what you can achieve with it. For instance how do you define a RegEx that parses the following expression correctly: 3 + 3*(x+3)/2. In addition RegEx code tend to be obscure and hard to decode, consider this common snippet for email verification:

^[a-zA-Z0-9.!#$%&'*+/=?^_`{|}~-]+@[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?(?:\.[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?)*$

In addition to being complicated it's also incomplete. More complete ones can be found here: Using a regular expression to validate an email address.

In addition RegEx tend not to produce any error messages to tell the user why an expression failed to parse.

Another common (incomplete & inefficient) parsing approach used by many is using String.Split to split the string on the operators.

For instance:

let r = 
  "1+2+3".Split '+'             // Produces an array: [|"1", "2", "3"|]
  |> Seq.map int                // Maps to seq of ints
  |> Seq.reduce (+)             // Reduces the seq using (+)

Taken to it's logical conclusion you can end up with a parser that looks like this

// Very inefficient, can't handle sub expressions, no error reporting...
//  Please use this as an illustration only, not production code
let stupidParse =
  let split (c: char) (s: string) = s.Split c
  let trim (s: string) = s.Trim ()
  let op c r f  = split c >> Seq.map (trim >> f) >> Seq.reduce r
  int |> op '/' (/) |> op '*' (*) |> op '-' (-) |> op '+' (+)

[<EntryPoint>]
let main argv = 
  let examples = [| "1"; "1-3"; "1*3"; "1 + 2*3 - 2" |]
  for example in examples do
    printfn "%s -> %d" example <| stupidParse example
  0

But as said in the comment I would never want a parser like this to enter production code. Use the proper tools like FsLex/FsYacc or FParsec.

Answer 2

I need to pass a sum in as a string into the console e.g. "4 + 5" and parse and calculate it.

If you are sure that your string is a sequence of numbers seperated by '+' and possibly white spaces, you can do something like this:

"4 + 5".Split '+' |> Seq.sumBy (int)

What does it do? .Split '+' separates the string by the character + and creates sequence of strings. In this example, the sequence would look like [|"4 "; " 5"|]. The function Seq.sumBy applies a given function to a each element of a sequence and sums up the result. We use the function (int) to convert strings to numbers.

Be aware that this solution fails miserably if the string either contains a character other than +, whitespace and digits or if a string without a digit is separated by + (e.g. + 7 + 8 or 7 ++ 8).

You might want to catch System.FormatException. You'd end up with something like

let sumString (input:string) : int = 
    try
        input.Split '+' |> Seq.sumBy (int)
    with
    | :? System.FormatException ->
        print "This does not look like a sum. Let's just assume the result is zero."
        0

This would just output 0 for any invalid formula. Another option to avoid the exception is throwing away all unwanted characters and empty strings:

 let sumString (input:System.String) : int = 
    (input |> String.filter (fun c -> ['0'; '1'; '2'; '3'; '4'; '5'; '6'; '7'; '8'; '9'; '+'] |> List.contains c)).Split '+'
    |> Seq.filter (((<) 0) << String.length)
    |> Seq.sumBy (int)

What does this code do? String.filter asks our anonymous function for every character whether it shall be considered. Our anonymous function checks whether the character is in a list of allowed characters. The result is a new string containing only digits and +. We split this string by +.

Before we pass our list of strings to Seq.sumBy (int), we filter our empty strings. This is done with Seq.filter and a composition of functions: (<) returns true if the first parameter is less than the second one. We use currying to obtain (<) 0, which checks whether the given integer is bigger than 0. We compose this function with String.length which maps a string to an integer telling its length.

After letting Seq.filter play with this function, we pass the resulting list to Seq.sumBy (int) as above.

This, however, might lead to quite surprising results for anything else than sums. "4 * 5 + 7" would yield 52.