Skip to content

Instantly share code, notes, and snippets.

@sideshowcoder
Created September 5, 2016 21:48
Show Gist options
  • Save sideshowcoder/9c00be4156ced8c269cabfd60a27a2d2 to your computer and use it in GitHub Desktop.
Save sideshowcoder/9c00be4156ced8c269cabfd60a27a2d2 to your computer and use it in GitHub Desktop.
F# Reverse Polish notation (RPN) Calculator
open System
type Token =
| Number of int
| UnaryOperator of (int -> int -> int)
let tryCharToToken a =
match (Int32.TryParse a) with
| (true, num) -> Some (Number num)
| (false, _) ->
match a with
| "*" -> Some (UnaryOperator (*))
| "+" -> Some (UnaryOperator (+))
| _ -> None
let tryProcessRpn equation =
let extractResult stack =
match stack with
| x :: [] -> Some x
| _ -> None
let rec processRec input stack =
match input with
| [] -> extractResult stack
| (Number x) :: xs -> processRec xs (x :: stack)
| (UnaryOperator op) :: xs -> applyOperator xs op stack
and applyOperator input operator stack =
match stack with
| l :: r :: rs -> processRec input ((operator l r) :: rs)
| _ -> None
processRec equation []
let evalRpn (s : String) =
let tokens = (s.Split [|' '|]) |> Array.toList
List.choose tryCharToToken tokens
|> tryProcessRpn
// Tests
let testExp exp expected =
match (evalRpn exp) with
| Some n ->
match expected with
| Some e -> if e = n then printf "." else printfn "\nExpected %i got %i for %s" e n exp
| None -> printfn "\nExpected None got %i for %s" n exp
| None ->
match expected with
| Some e -> printfn "\nExpected %i got None for %s" e exp
| None -> printf "."
let test () =
printfn "Running tests"
testExp "3 2 1 + *" (Some 9)
testExp "1 2 3" None
testExp "+" None
testExp "1 2 + +" (Some 3)
printfn "\nDone"
test ()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment