A simple string calculator in F#

Calculator.fs

namespace Calculator

open System

module Calculator =
    type Operator =
        | Add
        | Subtract
        | Multiply
        | Divide

    type Token =
        | OpenParen
        | CloseParen
        | Literal of decimal
        | Operator of Operator

    type TokenGroup =
        | Literal of decimal
        | Operator of Operator
        | Group of TokenGroup list

    type Expression =
        | Literal of decimal
        | Expression of Expression * Operator * Expression

    let tokenize (input: string): Token list =
        let chars = List.ofArray (input.ToCharArray())

        let parseLiteral (input: char list): Token * char list =
            let rec getLiteralString (input: char list) (literal: char list): char list * char list =
                match input with
                | '-'::rest when literal.Length = 0 ->
                    getLiteralString rest (['-'])
                | c::rest when (c >= '0' && c <= '9') || c = '.' ->
                    getLiteralString rest (literal @ [c])
                | _ -> (input, literal)

            let (remaining, literal) = getLiteralString input []
            let literalString = String.Concat(Array.ofList literal)
            let literalValue = Decimal.Parse literalString
            (Token.Literal(literalValue), remaining)

        let parseOpenParen (input: char list): Token * char list =
            (OpenParen, List.skip 1 input)

        let parseLiteralOrOpenParens (input: char list): Token * char list =
            match input with
            | '('::_ -> parseOpenParen input
            | _ -> parseLiteral input

        let parseOperatorOrCloseParen (input: char list): Token * char list =
            let firstChar = List.head input

            let token = match firstChar with
                        | '+' -> Token.Operator(Add)
                        | '-' -> Token.Operator(Subtract)
                        | '*' -> Token.Operator(Multiply)
                        | '/' -> Token.Operator(Divide)
                        | ')' -> CloseParen
                        | _ -> failwithf "Unrecognized input %c" firstChar

            (token, List.skip 1 input)

        let rec parse (input: char list) (tokens: Token list): Token list =
            let parser = match tokens with
                         | [] | Token.Operator(_)::_ | OpenParen::_ -> parseLiteralOrOpenParens
                         | Token.Literal(_)::_ | CloseParen::_ -> parseOperatorOrCloseParen

            let (token, remaining) = parser input
            let newTokens = (token::tokens)
            match remaining with
            | [] -> List.rev newTokens
            | _ -> parse remaining newTokens

        parse chars []

    let groupTokens (input: Token list): TokenGroup list =
        let rec group (input: Token list) (groups: TokenGroup list): TokenGroup list * Token list =
            let (|LiteralOrOperator|_|) (token: Token): TokenGroup option =
                match token with
                | Token.Literal(l) -> Some(TokenGroup.Literal(l))
                | Token.Operator(o) -> Some(TokenGroup.Operator(o))
                | _ -> None

            match input with
            | [] ->
                (groups, [])
            | LiteralOrOperator g::rest ->
                group rest (groups @ [g])
            | Token.OpenParen::rest ->
                let (groupedTokens, remaining) = group rest []
                let tokenGroup = TokenGroup.Group(groupedTokens)
                group remaining (groups @ [tokenGroup])
            | Token.CloseParen::rest ->
                (groups, rest)
            | _ ->
                failwithf "Unexpected sequence %A" input

        let (groups, _) = group input []
        groups

    let rec parse (groups: TokenGroup list): Expression =
        let (|LiteralOrGroup|_|) (input: TokenGroup): Expression option =
            match input with
            | TokenGroup.Literal(l) -> Some(Expression.Literal(l))
            | TokenGroup.Group(g) -> Some(parse(g))
            | _ -> None

        match groups with
        | [ LiteralOrGroup lhs; TokenGroup.Operator(o); LiteralOrGroup rhs ] ->
            Expression.Expression(lhs, o, rhs)
        | [ Group(g) ] ->
            parse(g)
        | [ TokenGroup.Literal(l) ] ->
            Expression.Literal(l)
        | _ ->
            failwithf "Unexpected pattern %A" groups

    let rec calculateExpression (expr: Expression): decimal =
        match expr with
        | Expression.Literal(l) -> l
        | Expression.Expression(lhs, o, rhs) ->
            let operator = match o with
                           | Add -> (+)
                           | Subtract -> (-)
                           | Multiply -> (*)
                           | Divide -> (/)
            operator (calculateExpression lhs) (calculateExpression rhs)

    let calculate (input: string): decimal =
        // example: "(1.5+(4.5--1.2))/2"

        let tokens = tokenize input

        // [ OpenParen; Literal(1.5); Operator(Add); OpenParen; Literal(4.5); Operator(Subtract); Literal(-1.2); CloseParen; CloseParen; Operator(Divide); Literal(2) ]

        let groups = groupTokens tokens

        // [ Group([Literal(1.5); Operator(Add); Group([Literal(4.5); Operator(Subtract); Literal(-1.2)])]); Operator(Divide); Literal(2) ]

        let expression = parse groups
        // Expression(Expression(Literal(1.5), Operator.Add, Expression(Literal(4.5), Operator.Subtract, Literal(-1.2)), Operator.Divide, Literal(2))

        calculateExpression expression

        // 3.6m