Reverse Polish Notation in F#

In my question to learn F#, I've decided to get one step closer to creating a programming language, and implement this simple Reverse Polish Notation "interpreter" of sorts.

It does not allow for parentheses in input ( ), and only accepts expressions containing the following valid tokens:

0 1 2 3 4 5 6 7 8 9 + - * /

Here's a small list of sample inputs and outputs for reference:

• 2 2 + -> 4

• 10 10 + 5 * -> 100

• 2 2 4 + 2 -> 16

I have a few concerns here:

• Is this written in a proper "functional" way?

• Is there any way to shorten evaluate_expr?

• Are there any glaring issues that I missed?

```
open System
open System.Collections.Generic
open System.Text.RegularExpressions

///
/// Evaluate an expression pair, like '2 2 +'.
///
/// The operand to use.
let evaluate_expr_pair (a: string) (b: string) (operand: string) =
match operand with
| "+" -> (Int64.Parse(a) + Int64.Parse(b)).ToString()
| "-" -> (Int64.Parse(a) - Int64.Parse(b)).ToString()
| "" -> (Int64.Parse(a) Int64.Parse(b)).ToString()
| "/" -> (Int64.Parse(a) / Int64.Parse(b)).ToString()
| _ -> ""

///
/// Evaluate a tokenized expression, such as '[| "2"; "2"; "+" |]',
/// and return a result, in this case, '2'.
///
/// The expression to evaluate.
let evaluate_expr (expr: string[]) =
let program_stack = new Stack()

for token in expr do
program_stack.Push(token)

match token with
| "+" -> let operand = program_stack.Pop()
let b = program_stack.Pop()
let a = program_stack.Pop()
program_stack.Push(evaluate_expr_pair a b operand)

| "-" -> let operand = program_stack.Pop()
let b = program_stack.Pop()
let a = program_stack.Pop()
program_stack.Push(evaluate_expr_pair a b operand)

| "*" -> let operand = program_stack.Pop()
let b = program_stack.Pop()
let a = progr

evaluate_expr_pair

Your calculator performs integer division, which is a bit surprising. To fix it to do floating-point or decimal arithmetic, though, you would have to do a search-and-replace of Int64.Parse, which has been written an unreasonable number of times in evaluate_expr_pair.

evaluate_expr_pair also does a lot of Parse and ToString round trips. Not only is that inefficient, it could also cost you some loss of precision if you were doing floating-point arithmetic.

operand should really be called operator. (The operands are a and b.) Ignoring unrecognized operators is a bad idea, even if you have validated the input in check_expr. If not doing exception handling, I'd rather leave out the default case and let it crash. I'd also prefer to detect errors while attempting to evaluate the expression than pre-validate, because there are some errors that you can't reasonably detect without evaluating the expression (such as stack underflow).

evaluate_expr

Here, with your use of the program_stack, you are venturing outside the realm of functional programming, because the .Push() and .Pop() operations cause mutation. A more FP approach would be to use a List as an immutable stack.

Instead of blindly pushing tokens, some of which are operators, onto a stack of strings, you should only put numeric data in the stack.

You would be better off treating the operators as functions that manipulate the entire stack directly, instead of as functions that take two operands and return one result. Otherwise, you would have to implement an operation like swap as a special case, and distinguish between binary operations and unary operations such as negate and ex.

tokenize_expr

The simple strategy would be to use new Regex("\s+") as the delimiter pattern. You're treating the operators as captured delimiters — presumably to make spaces optional in an expression like 1 2+ — and discarding the last element of the resulting array. That works, as long as the expression ends with an operator. If the expression is just 5, for example, you'll discard a number.

The regex could be written more succinctly using a [-+*/] character class. I wouldn't bother naming split_pattern and split_regex as variables.

main

printf is preferred over System.Console.Write.

If you going to set up a |> pipeline, don't interrupt it by defining let tokenized_expr — that just gets in the way.

Summary

RPN calculators are much simpler when the operators work directly on the stack, rather than having a controller feed the operands to them. In fact, every function except main has traces of the operator definitions.

Here's an implementation that I came up with:

open System
open System.Text.RegularExpressions

exception InputError of string

let tokenize (expr: string) =
    expr |> (new Regex("\s+|\s*([-+*/])\s*")).Split
         |> Array.toList
         |> List.filter(fun s -> s.Length > 0)

let perform (op: string) (stack: decimal list) =
    match (op, stack) with
    | ("+",     a :: b :: cs) -> (b + a) :: cs
    | ("-",     a :: b :: cs) -> (b - a) :: cs
    | ("*",     a :: b :: cs) -> (b * a) :: cs
    | ("/",     a :: b :: cs) -> (b / a) :: cs
    | ("swap",  a :: b :: cs) -> b :: a  :: cs
    | ("drop",  a :: cs)      -> cs
    | ("roll",  a :: cs)      -> cs @ [a]
    | (n,       cs)           ->
        try
            decimal n :: cs
        with
            | :? System.FormatException -> raise (InputError(n))

let evaluate (expr: string list) =
    let rec evaluate' (expr: string list) (stack: decimal list) =
        match expr with
        | []        -> stack
        | op :: exp -> evaluate' exp (perform op stack)
    evaluate' expr []

[]
let main argv = 
    while true do
        printf ": "
        try
            match Console.ReadLine() |> tokenize |> evaluate with
            | num :: []  -> num   |> printfn "%g"       // Single answer
            | stack      -> stack |> printfn "%O"       // Junk left on stack
        with
        | InputError(str) -> printfn "Bad input: %s" str
    0

StackExchange Code Review Q#99150, answer score: 3