Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 37 ยท Projects and Practice

Project: Expression Evaluator

Build a calculator in F#: tokenize text with a list of unions, parse with recursive descent and precedence, evaluate the tree with pattern matching, report errors with Result, and simplify expressions.

F# was built for this: languages and interpreters. In this project you write a calculator that reads 2 + 3 * (4 - 1) and prints 11. Along the way you use a tokenizer (text to tokens), a parser (tokens to a tree) and an evaluator (tree to a value). Each stage is a small pure function working on unions, and the stages connect with Result, which makes this a good revision of unions, pattern matching and Result.

The F# code is read-only here; a C# version of the finished program runs below so you can try expressions.

Stage 1: tokens

FSHARP
type Token =
    | Number of float
    | Plus
    | Minus
    | Star
    | Slash
    | LParen
    | RParen

let tokenize (input: string) : Result<Token list, string> =
    let rec go (chars: char list) acc =
        match chars with
        | [] -> Ok (List.rev acc)
        | c :: rest when System.Char.IsWhiteSpace c -> go rest acc
        | '+' :: rest -> go rest (Plus :: acc)
        | '-' :: rest -> go rest (Minus :: acc)
        | '*' :: rest -> go rest (Star :: acc)
        | '/' :: rest -> go rest (Slash :: acc)
        | '(' :: rest -> go rest (LParen :: acc)
        | ')' :: rest -> go rest (RParen :: acc)
        | c :: _ when System.Char.IsDigit c ->
            let digits = chars |> List.takeWhile (fun x -> System.Char.IsDigit x || x = '.')
            let text = System.String(List.toArray digits)
            let remaining = List.skip digits.Length chars
            go remaining (Number (float text) :: acc)
        | c :: _ -> Error $"unexpected character '{c}'"
    go (List.ofSeq input) []

The function walks a list of characters with a recursive helper, the typical F# idiom: the list pattern c :: rest takes one char, and an accumulator acc builds the output backwards (then List.rev). A literal char pattern like '+' matches directly. Numbers use a guard and List.takeWhile to read all digits and dots. Any other character produces an Error.

Stage 2: the syntax tree

FSHARP
type Expr =
    | Num of float
    | Neg of Expr
    | Add of Expr * Expr
    | Sub of Expr * Expr
    | Mul of Expr * Expr
    | Div of Expr * Expr

Stage 3: parsing with precedence

We use recursive descent, one function per precedence level. Lowest precedence is addition and subtraction, then multiplication and division, then unary minus and the smallest units (numbers and parentheses):

flowchart TD
    E["expr: term (+|- term)*"] --> T["term: factor (*|/ factor)*"]
    T --> F["factor: number | ( expr ) | - factor"]
    F -->|"parentheses"| E

The grammar. Because expr calls term, which calls factor, multiplication binds tighter than addition, and parentheses jump back to the top.

Each parse function takes the remaining tokens and returns the tree and the tokens it did not consume:

FSHARP
let rec parseExpr tokens : Result<Expr * Token list, string> =
    parseTerm tokens
    |> Result.bind (fun (left, rest) -> loopExpr left rest)

and loopExpr left tokens =
    match tokens with
    | Plus :: rest ->
        parseTerm rest |> Result.bind (fun (right, rest') -> loopExpr (Add (left, right)) rest')
    | Minus :: rest ->
        parseTerm rest |> Result.bind (fun (right, rest') -> loopExpr (Sub (left, right)) rest')
    | _ -> Ok (left, tokens)

and parseTerm tokens =
    parseFactor tokens
    |> Result.bind (fun (left, rest) -> loopTerm left rest)

and loopTerm left tokens =
    match tokens with
    | Star :: rest ->
        parseFactor rest |> Result.bind (fun (right, rest') -> loopTerm (Mul (left, right)) rest')
    | Slash :: rest ->
        parseFactor rest |> Result.bind (fun (right, rest') -> loopTerm (Div (left, right)) rest')
    | _ -> Ok (left, tokens)

and parseFactor tokens =
    match tokens with
    | Number n :: rest -> Ok (Num n, rest)
    | Minus :: rest -> parseFactor rest |> Result.map (fun (e, r) -> Neg e, r)
    | LParen :: rest ->
        parseExpr rest
        |> Result.bind (fun (e, remaining) ->
            match remaining with
            | RParen :: after -> Ok (e, after)
            | _ -> Error "expected ')'")
    | [] -> Error "unexpected end of input"
    | t :: _ -> Error $"unexpected token {t}"

let parse tokens =
    parseExpr tokens
    |> Result.bind (fun (e, rest) ->
        if List.isEmpty rest then Ok e else Error "unexpected trailing input")

The group is mutually recursive (let rec ... and ...), because an expression contains terms, terms contain factors and a factor can contain a whole expression in parentheses. The loops make + and - left-associative: 10 - 3 - 2 becomes Sub (Sub (10, 3), 2), which equals 5, not 9.

Stage 4: evaluating

FSHARP
let rec eval expr : Result<float, string> =
    match expr with
    | Num n -> Ok n
    | Neg e -> eval e |> Result.map (fun v -> -v)
    | Add (a, b) -> binary (+) a b
    | Sub (a, b) -> binary (-) a b
    | Mul (a, b) -> binary (*) a b
    | Div (a, b) ->
        eval b
        |> Result.bind (fun d ->
            if d = 0.0 then Error "division by zero"
            else eval a |> Result.map (fun n -> n / d))

and binary op a b =
    eval a |> Result.bind (fun x -> eval b |> Result.map (fun y -> op x y))

let calculate input =
    tokenize input
    |> Result.bind parse
    |> Result.bind eval

calculate is the pipeline: tokenize, parse and eval are connected with Result.bind, so an error at any stage skips the rest. That is the railway from the Result lesson in action. In FSI:

FSHARP
calculate "2 + 3 * (4 - 1)"   // Ok 11.0
calculate "10 / (5 - 5)"      // Error "division by zero"
calculate "2 + "              // Error "unexpected end of input"
calculate "2 $ 3"             // Error "unexpected character '$'"
C# C# version of the whole calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Stage 5: simplify and print

Because the tree is data, you can transform it. A simplifier rewrites patterns it recognises:

FSHARP
let rec simplify expr =
    match expr with
    | Add (Num 0.0, e) | Add (e, Num 0.0) -> simplify e
    | Mul (Num 1.0, e) | Mul (e, Num 1.0) -> simplify e
    | Mul (Num 0.0, _) | Mul (_, Num 0.0) -> Num 0.0
    | Add (a, b) -> Add (simplify a, simplify b)
    | Mul (a, b) -> Mul (simplify a, simplify b)
    | Sub (a, b) -> Sub (simplify a, simplify b)
    | Div (a, b) -> Div (simplify a, simplify b)
    | Neg e -> Neg (simplify e)
    | Num _ -> expr

This is the style compilers use: nested patterns that read like algebra rules. A show function that turns the tree back into text is a good exercise for pattern matching with precedence.

Ideas to extend it

  1. Add ^ for powers (right-associative) and the functions sqrt and abs with a new token Ident of string.
  2. Add variables and an environment Map<string, float>; eval takes the map.
  3. Keep source positions in tokens and report errors as "column 7: expected ')'".
  4. Write FsCheck properties: eval (simplify e) = eval e for random trees.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What are the three stages of the evaluator, in order?

    Text becomes tokens, tokens become a tree, and the tree becomes a value.
  2. 2. How does the grammar make * bind tighter than +?

    Each precedence level is its own function, and the lower-precedence one calls the higher-precedence one.
  3. 3. Why are the parse functions declared with let rec ... and ...?

    expr, term and factor call each other, so they must be declared together.
  4. 4. What does connecting the stages with Result.bind achieve?

    bind passes an Error through untouched, so a failure at any stage surfaces at the end.

Summary

  • A tokenizer, a parser and an evaluator are three small pure functions over unions.
  • Recursive descent encodes precedence: one function per level, loops for left associativity.
  • Result.bind links the stages so errors flow through without exception handling.
  • Trees are data, so simplifying or printing them is just more pattern matching.

Next: Project: Text Statistics