A RPN Calculator in F#

While continuing my journey in F#, after playing with Project Eulero problems for a few weeks, I have come across another excellent  excercise site which goes under the name of Programming Praxis.

The first exercise requires to implement a simple calculator using Reverse Polish Notation (RPN).

Here follows a simple solution to the problem. Operands are pushed onto the stack until an operator is found: at that point the last two operands are popped from the stack, the operator is applied to them and the result is pushed back on the stack.

#light

let is_operator c =
    match c with
        | "+" | "-" | "*" | "/"  -> true
        | _ -> false

let calculate left operator right =
    match operator with
        | "+" -> left + right
        | "-" -> left - right
        | "*" -> left * right
        | "/" -> left / right
        | _ -> failwith "Unknown operator"

let proc (item:string) (stack:System.Collections.Generic.Stack<double>) =
    if is_operator item then
        let r = stack.Pop() 
        let l = stack.Pop() 
        let result = calculate l item r
        stack.Push result
    else
        stack.Push(System.Convert.ToDouble(item))

let evaluate (expression:string) =
    let stack = new System.Collections.Generic.Stack<double>()
    let items = expression.Split([|' ' |]) 
    Array.iter (fun i -> proc i stack) items
    stack.Pop()
  • We first define a simple function to check whether a given string is to be interpreted as an arithmetic operand. As you can see, we only support basic operators, nothing too fancy.
  • We then define a function which takes a double, a string (representing an operator) and another double, and returns the result of applying the given operator to the two numbers.
  • The proc function takes a string, which represent either an operand or an operator, and a stack of operands.

    If the item contained in the string is an operator, two operands are popped from the stack: the first pop is for the right side operand and the second pop is for the left operand; hence, the operator is applied to the two operands and the result is pushed back onto the stack.

    Otherwise, if it’s an operand, it’s first converted from the string format and pushed onto the stack.

  • Finally, the entrance point to the program is defined with the evaluate function, which
    • accepts a string containing the overall expression (such as “1 2 + 4 / 5 * 6 -”)
    • splits the string into an array of token strings
    • feed each token into the proc function
    • finally pops the stack with the last operand to yield the result of the operation.

kick it on DotNetKicks.com

Shout it

This entry was posted in .NET, F# and tagged , , . Bookmark the permalink.
  • Pingback: DotNetShoutout

  • Pingback: Rick Minerich's Development Wonderland : F# Discoveries This Week 10/03/2010

  • Fred

    Similar to one I saw on some other blog:

    let digit v = function x :: t -> 10 * x + v :: t
    let binary f = function _ :: a :: b :: t -> f b a :: t
    let codes =
    Map.ofList [
    '0', digit 0
    '1', digit 1
    '2', digit 2
    '3', digit 3
    '4', digit 4
    '5', digit 5
    '6', digit 6
    '7', digit 7
    '8', digit 8
    '9', digit 9
    '+', binary (+)
    '-', binary (-)
    '*', binary (*)
    '/', binary (/)
    ' ', fun s -> 0 :: s]
    let flip f a b = f b a
    let compile = flip Map.find codes |> Seq.map
    let execute = Seq.fold (|>)
    let eval = compile >> execute [0] >> Seq.head
    let rec repl () = Console.ReadLine() |> eval |> printf “%in>” |> repl
    printf “n>”
    repl ()