Skip to content

Instantly share code, notes, and snippets.

@marcin-chwedczuk
Created May 26, 2018 17:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save marcin-chwedczuk/70d5425a63a3ec4635c7b455d98859d4 to your computer and use it in GitHub Desktop.
Save marcin-chwedczuk/70d5425a63a3ec4635c7b455d98859d4 to your computer and use it in GitHub Desktop.
fsharp-primitive-expression-evaluator
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment