fsharp-primitive-expression-evaluator

eval.fs

open System
open System.Collections.Generic
open System.Diagnostics
open System.Reflection
open System.Text.RegularExpressions

type Operator =
    | Plus | Minus | Multiply | Divide

type Token =
    | StartBracket
    | EndBracket
    | Op of Operator
    | Number of int

let tokenize (input:string) =
    let pattern = @"([-+*/()])";
    let rawTokens = Regex.Split(input, pattern)
    let notEmpty s = not (String.IsNullOrEmpty(s))
    rawTokens 
        |> Array.toList 
        |> List.filter notEmpty
        |> List.map (function 
            | "+" -> Op Plus
            | "-" -> Op Minus
            | "*" -> Op Multiply
            | "/" -> Op Divide
            | "(" -> StartBracket
            | ")" -> EndBracket
            | _ as number -> Number (int number))

type Expr =
    | Value of int
    | UnaryOp of Operator * Expr
    | BinaryOp of Operator * Expr * Expr
    
let parse (tokens : Token list) =
    let binary op expr1 expr2 = (BinaryOp(op, expr1, expr2))
    
    let rec parseExpr ts : (Expr * Token list) =
        match ts with 
        | StartBracket::ts ->
            let (expr, ts) = parseExpr ts
            match ts with 
            | EndBracket::ts -> (expr, ts)
            | _ -> failwith "Expecting )"
        | _ -> parseAdditive ts
        
    and parseAdditive ts : (Expr * Token list)  =
        let (expr, ts) = parseMultiplicative ts
        
        let rec parseChain expr ts =
            match ts with 
            | (Op Plus)::ts -> 
                let (nextExpr, ts) = parseMultiplicative ts
                parseChain (binary Plus expr nextExpr) ts
            | (Op Minus)::ts ->
                let (nextExpr, ts) = parseMultiplicative ts
                parseChain (binary Minus expr nextExpr) ts
            | _ -> (expr, ts)
            
        parseChain expr ts
        
    and parseMultiplicative ts : (Expr * Token list)  =
        let (expr, ts) = parseUnary ts
        
        let rec parseChain expr ts =
            match ts with 
            | (Op Multiply)::ts ->
                let (nextExpr, ts) = parseUnary ts
                parseChain (BinaryOp(Multiply, expr, nextExpr)) ts
            | (Op Divide)::ts ->
                let (nextExpr, ts) = parseUnary ts
                parseChain (BinaryOp(Divide, expr, nextExpr)) ts
            | _ -> (expr, ts) 
        
        parseChain expr ts
        
    and parseUnary ts =
        let unary op (expr,ts) = (UnaryOp(op,expr), ts)
        match ts with 
        | [] -> failwith "Expecting number but EOF reached."
        | (Number n)::ts -> (Value n, ts)
        | (Op Plus)::ts -> unary Plus (parseUnary ts)
        | (Op Minus)::ts -> unary Minus (parseUnary ts)
        | StartBracket::_ -> parseExpr ts
        | t::_ -> failwithf "Unexpected token: %A. Expecting unary + or -." t
            
    let (expr, ts) = parseExpr tokens
    if not (List.isEmpty ts) 
        then failwithf "Unexpected tokens: %A." ts
    expr
    
let rec eval (expr: Expr) =
    match expr with 
    | Value n -> n
    | UnaryOp(Plus, expr) -> eval expr
    | UnaryOp(Minus,expr) -> -(eval expr)
    | BinaryOp(Plus, e1, e2) -> (eval e1) + (eval e2)
    | BinaryOp(Minus, e1, e2) -> (eval e1) - (eval e2)
    | BinaryOp(Multiply, e1, e2) -> (eval e1) * (eval e2)
    | BinaryOp(Divide, e1, e2) -> (eval e1) / (eval e2)
    | _ -> failwithf "Invalid expression tree: %A" expr

[<EntryPoint>]
let main argv =
    let input = "-3+85*(7/2)+(8)"
    let tokens = tokenize input
    let expr = parse tokens
    let value = eval expr 
    printfn "%s = %d" input value
    0