Reverse Polish Notation in F#

Question

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

/// <summary>
/// Evaluate an expression pair, like '2 2 +'.
/// <summary>
/// <param name="operand">The operand to use.</param>
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()
    | _ -> ""

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

    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 = 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)

        | _ -> ()

    program_stack.Pop()

/// <summary>
/// Tokenize an input expression, such as '2 2 + 5 *'.
/// </summary>
/// <param name="expr">The expression to tokenize.</param>
let tokenize_expr (expr: string) =
    let split_pattern = "\s*(\+|\-|\*|\/)\s*|\s+"
    let split_regex = new Regex(split_pattern)
    let result = split_regex.Split(expr)
    result.[0..result.Length - 2]

/// <summary>
/// Check all the tokens of an expression to make sure
/// that they are all legal.
/// </summary>
/// <param name="expr">The expression to check.</param>
let check_expr (expr: string) =
    let valid_token_pattern = "[\s0-9\+\-\*\/]"
    let valid_token_regex = new Regex(valid_token_pattern)

    for token in expr do
        if valid_token_regex.Match(token.ToString()).Success then
            ()
        else
            Console.WriteLine(String.Format("Invalid token \"{0}\".", token))

[<EntryPoint>]
let main argv = 
    while true do
        Console.Write(": ")
        let input_expr = Console.ReadLine()

        input_expr |> check_expr
        let tokenized_expr = input_expr |> tokenize_expr
        let result = tokenized_expr |> evaluate_expr

        Console.Write("\n ")
        Console.Write(result)
        Console.Write("\n\n")
    0

Answer 1

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 e^x.

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 []

[<EntryPoint>]
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

Answer 2

As mentioned in the comments, the match block can definitely be reduced. I have no knowledge of F#, but after looking at the docs for match, we can see that it is possible to match multiple branches to one content. The revised block:

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)
| _ -> ()

But this still doesn't look good, now as a design problem more than a repetition one: The operations are repeated in at least two places. I don't know how would you do it with F#, but in C#, I'd use a Dictionary<char, Func<int, int, int>> (that is, a dictionary with key char, and values as functions that take 2 ints and return a int).

Then, you would just check if the key is in the dictionary, and if it is, call the said function. Pseudocode:

if token in operation_map.keys
    operand = stack.pop()
    b = stack.pop()
    a = stack.pop()
    stack.push(operation_map[operand](a, b))

And finally, I would only conditionally push the token, since if it is a valid operand, its going to be popped anyway. Updated body of for, in pseudocode:

for token in expr
    if token in operation_map.keys
        b = stack.pop()
        a = stack.pop()
        stack.push(operation_map[token](a, b)) //note that `token` is used here.
    else
        stack.push(token)

This way, you don't need to push a operand only to pop it.

Finally, your check_expr function's if looks a bit weird. just negate the condition, and drop the else! (assuming () is syntax for "do nothing")

Disclaimer:

I know absolutely nothing about F# and its capabilities, nor do I commonly use the functional paradigm. Maybe my suggestions are not entirely fitting.