How to fix this bug in a math expression evaluator

Question

I've written a typical evaluator for simple math expressions (arithmetic with some custom functions) in F#. While it seems to be working correctly, some expressions don't evaluate as expected, for example, these work fine:

• eval "5+2" --> 7
• eval "sqrt(25)^2" --> 25
• eval "1/(sqrt(4))" --> 0.5
• eval "1/(2^2+2)" --> 1/6 ~ 0.1666...

but these don't:

• eval "1/(sqrt(4)+2)" --> evaluates to 1/sqrt(6) ~ 0.408...
• eval "1/(sqrt 4 + 2)" --> will also evaluate to 1/sqrt(6)
• eval "1/(-1+3)" --> evaluates to 1/(-4) ~ -0.25

the code works as follows, tokenization (string as input) -> to rev-polish-notation (RPN) -> evalRpn

I thought that the problem seems to occur somewhere with the unary functions (functions accepting one operator), these are the sqrt function and the negation (-) function. I don't really see what's going wrong in my code. Can someone maybe point out what I am missing here?

this is my implementation in F#

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) 

Answer 1

Before answering your specific question, did you notice you have another bug? Try eval "2-4" you get 2.0 instead of -2.0.

That's probably because along these lines:

match op with
    | Plus -> Num(v + u)
    | Minus -> Num(v - u)
    | Star -> Num(v * u)
    | Slash -> Num(u / v)
    | Hat -> Num(u ** v)

u and v are swapped, in commutative operations you don't notice the difference, so just revert them to u -v.

Now regarding the bug you mentioned, the cause seems obvious to me, by looking at your code you missed the precedence of those unary operations:

let prec = function
    | Hat -> 3
    | Star | Slash -> 2
    | Plus | Minus -> 1
    | _ -> 0

I tried adding them this way:

let prec = function
    | Negative -> 5
    | Sqrt -> 4
    | Hat -> 3
    | Star | Slash -> 2
    | Plus | Minus -> 1
    | _ -> 0

And now it seems to be fine.

Answer 2

Edit: meh, seems I was late, Gustavo posted the answer while I was wondering about the parentheses. Oh well.

• Unary operators have the wrong precedence. Add the primary case | a when isUnary a -> 4 to prec.

• The names of LParen and RParen are consistently swapped throughout the code. ( maps to RParen and ) to LParen!

It runs all tests from the question properly for me, given the appropriate precedence, but I haven't checked the code for correctness.