Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- open System.Collections
- open System.Collections.Generic
- open System.Text.RegularExpressions
- type Token =
- | Num of float
- | Plus
- | Minus
- | Star
- | Hat
- | Sqrt
- | Slash
- | Negative
- | RParen
- | LParen
- let hasAny (list: Stack<'T>) =
- list.Count <> 0
- let tokenize (input:string) =
- let tokens = new Stack<Token>()
- let push tok = tokens.Push tok
- let regex = new Regex(@"[0-9]+(.+d*)?|+|-|*|/|^|)|(|pi|e|sqrt")
- for x in regex.Matches(input.ToLower()) do
- match x.Value with
- | "+" -> push Plus
- | "*" -> push Star
- | "/" -> push Slash
- | ")" -> push LParen
- | "(" -> push RParen
- | "^" -> push Hat
- | "sqrt" -> push Sqrt
- | "pi" -> push (Num System.Math.PI)
- | "e" -> push (Num System.Math.E)
- | "-" ->
- if tokens |> hasAny then
- match tokens.Peek() with
- | LParen -> push Minus
- | Num v -> push Minus
- | _ -> push Negative
- else
- push Negative
- | value -> push (Num (float value))
- tokens.ToArray() |> Array.rev |> Array.toList
- let isUnary = function
- | Negative | Sqrt -> true
- | _ -> false
- let prec = function
- | Hat -> 3
- | Star | Slash -> 2
- | Plus | Minus -> 1
- | _ -> 0
- let toRPN src =
- let output = new ResizeArray<Token>()
- let stack = new Stack<Token>()
- let rec loop = function
- | Num v::tokens ->
- output.Add(Num v)
- loop tokens
- | RParen::tokens ->
- stack.Push RParen
- loop tokens
- | LParen::tokens ->
- while stack.Peek() <> RParen do
- output.Add(stack.Pop())
- stack.Pop() |> ignore // pop the "("
- loop tokens
- | op::tokens when op |> isUnary ->
- stack.Push op
- loop tokens
- | op::tokens ->
- if stack |> hasAny then
- if prec(stack.Peek()) >= prec op then
- output.Add(stack.Pop())
- stack.Push op
- loop tokens
- | [] ->
- output.AddRange(stack.ToArray())
- output
- (loop src).ToArray()
- let (@) op tok =
- match tok with
- | Num v ->
- match op with
- | Sqrt -> Num (sqrt v)
- | Negative -> Num (v * -1.0)
- | _ -> failwith "input error"
- | _ -> failwith "input error"
- let (@@) op toks =
- match toks with
- | Num v,Num u ->
- match op with
- | Plus -> Num(v + u)
- | Minus -> Num(v - u)
- | Star -> Num(v * u)
- | Slash -> Num(u / v)
- | Hat -> Num(u ** v)
- | _ -> failwith "input error"
- | _ -> failwith "inpur error"
- let evalRPN src =
- let stack = new Stack<Token>()
- let rec loop = function
- | Num v::tokens ->
- stack.Push(Num v)
- loop tokens
- | op::tokens when op |> isUnary ->
- let result = op @ stack.Pop()
- stack.Push result
- loop tokens
- | op::tokens ->
- let result = op @@ (stack.Pop(),stack.Pop())
- stack.Push result
- loop tokens
- | [] -> stack
- if loop src |> hasAny then
- match stack.Pop() with
- | Num v -> v
- | _ -> failwith "input error"
- else failwith "input error"
- let eval input =
- input |> (tokenize >> toRPN >> Array.toList >> evalRPN)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement