Some coding fun - The expression tree challenge :)

I thought I would have some fun a create a syntax tree for simple calculations to show how expressive F# can be with a tiny amount of code.

The challenge should you accept it is post implementations in other languages. It is always interesting seeing how other languages handle different tasks.

So on to the f#. First I have a type that shows how I store the syntax.

type Expression =
    | Number of float
    | Add of Expression * Expression
    | Subtract of Expression * Expression
    | Multiply of Expression * Expression
    | Divide of Expression * Expression

Think of Expression like an abstract base class and the types below it inherit off it. This is an F# union type.

Number stores a float value. The rest represent operations and store to expressions, the lhs and rhs in normal math notation. You can see how they nest into a tree. A very powerful and terse type that OO languages need inho.

Next up how I parse, a recursive function that performs a different action for each expression type. If it is a number that value is returned. For the others it parses the two expressions by calling into itself. It then performs the related operation on the results.

let rec parseTree expression =
    match expression with
    | Number value -> value
    | Add (ex1, ex2) -> ((parseTree ex1) + (parseTree ex2))
    | Subtract (ex1, ex2) -> ((parseTree ex1) - (parseTree ex2))
    | Multiply (ex1, ex2) -> ((parseTree ex1) * (parseTree ex2))
    | Divide (ex1, ex2) -> ((parseTree ex1) / (parseTree ex2))

Here is the definition of an expression. I have added where all the brackets in the expression are in the comment above it.

//  (((5 + (1.5 * 2.0)) + 6) / 2)
let tree = 
    Divide(Add(Add(Number 5.0, Multiply(Number 1.5,Number 2.0)),Number 6.0),Number 2.0)

Run it and the result is 7, as expected.

[<EntryPoint>]
let main argv = 
    printfn "%f" (parseTree tree)
    0 // return an integer exit code

Post your solutions in other languages :)

Woz