1 people like it.

Evaluating random arithemtic expressions

Generate a random expression and evaluate it

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70: 
71: 
72: 
73: 
74: 
75: 
76: 
77: 
78: 
79: 
80: 
81: 
82: 
83: 
84: 
85: 
86: 
87: 
88: 
89: 
module fs
    
open NUnit.Framework
open FsUnit
open System
open System.Data
    
type Operation = 
    | Mult 
    | Sub
    | Add
    override this.ToString() = 
        match this with  
            | Mult -> "*" 
            | Sub -> "-" 
            | Add -> "+"
    member this.evaluate = 
        match this with  
            | Mult -> (*) 
            | Sub -> (-) 
            | Add -> (+)
    
let orderofOps = [[Mult];[Add;Sub]]

type Expression = 
    | Terminal of int    
    | Expr of Expression * Operation * Expression
    
let rand = new System.Random()
    
let randNum min max = rand.Next(min, max)
    
let randomOperation () = 
    match randNum 0 2 with 
    | 0 -> Mult 
    | 1 -> Sub  
    | _ -> Add

let (|TermWithExpression|_|) predicate expr  = 
       match expr with 
        | Expr(Terminal(left), targetOp, Expr(Terminal(right), o, next)) 
            when predicate targetOp -> Expr(Terminal(targetOp.evaluate left right), o, next) |> Some
        | _ -> None

let (|TermWithTerm|_|) predicate expr = 
    match expr with 
        | Expr(Terminal(item), targetOp, Terminal(item2)) 
                when predicate targetOp -> 
                    Terminal(targetOp.evaluate item item2) |> Some
        | _ -> None

let foldExpr expr opsInPrecedence = 
    let rec foldExpr' expr = 
        let shouldEvalOperator o = List.exists (fun i -> i = o) opsInPrecedence

        match expr with 
            | TermWithExpression shouldEvalOperator output -> foldExpr' output    
            | TermWithTerm shouldEvalOperator output -> output
            | Expr(left, o, right) -> Expr(foldExpr' left, o, foldExpr' right)            
            | Terminal(i) -> Terminal(i)

    foldExpr' expr
    
let rec randomExpression min max length = 
    match length with 
        | 0 -> Terminal(randNum min max)
        | _ -> Expr(Terminal(randNum min max), randomOperation(), randomExpression min max (length - 1))
    
let rec display = function
        | Terminal(i) -> i.ToString()
        | Expr(i, op, exp) -> System.String.Format("{0} {1} {2}",display i, op,display exp)        
    
let eval e = List.fold foldExpr e orderofOps
    
[<Test>]
let arithmeticTest() =
 
    let dt = new DataTable()    

    for i in [0..100] do
        let randomExpr = randomExpression 0 10 5

        let validationResult = dt.Compute(display randomExpr, "").ToString() |> Convert.ToInt32
    
        let result = eval randomExpr
            
        printfn "%s = %d = %d" (display randomExpr) validationResult (match result with Terminal(x) -> x)
    
        result |> should equal <| Terminal(validationResult)
module fs
namespace NUnit
namespace NUnit.Framework
namespace FsUnit
namespace System
namespace System.Data
type Operation =
  | Mult
  | Sub
  | Add
  override ToString : unit -> string
  member evaluate : (int -> int -> int)

Full name: fs.Operation
union case Operation.Mult: Operation
union case Operation.Sub: Operation
union case Operation.Add: Operation
val this : Operation
override Operation.ToString : unit -> string

Full name: fs.Operation.ToString
member Operation.evaluate : (int -> int -> int)

Full name: fs.Operation.evaluate
val orderofOps : Operation list list

Full name: fs.orderofOps
type Expression =
  | Terminal of int
  | Expr of Expression * Operation * Expression

Full name: fs.Expression
union case Expression.Terminal: int -> Expression
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
union case Expression.Expr: Expression * Operation * Expression -> Expression
val rand : Random

Full name: fs.rand
Multiple items
type Random =
  new : unit -> Random + 1 overload
  member Next : unit -> int + 2 overloads
  member NextBytes : buffer:byte[] -> unit
  member NextDouble : unit -> float

Full name: System.Random

--------------------
Random() : unit
Random(Seed: int) : unit
val randNum : min:int -> max:int -> int

Full name: fs.randNum
val min : int
val max : int
Random.Next() : int
Random.Next(maxValue: int) : int
Random.Next(minValue: int, maxValue: int) : int
val randomOperation : unit -> Operation

Full name: fs.randomOperation
val predicate : (Operation -> bool)
val expr : Expression
val left : int
val targetOp : Operation
val right : int
val o : Operation
val next : Expression
property Operation.evaluate: int -> int -> int
union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
val item : int
val item2 : int
val foldExpr : expr:Expression -> opsInPrecedence:Operation list -> Expression

Full name: fs.foldExpr
val opsInPrecedence : Operation list
val foldExpr' : (Expression -> Expression)
val shouldEvalOperator : (Operation -> bool)
Multiple items
type List =
  new : unit -> List
  static member Map : actual:ICollection -> ListMapper

Full name: NUnit.Framework.List

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

--------------------
List() : unit
val exists : predicate:('T -> bool) -> list:'T list -> bool

Full name: Microsoft.FSharp.Collections.List.exists
val i : Operation
active recognizer TermWithExpression: (Operation -> bool) -> Expression -> Expression option

Full name: fs.( |TermWithExpression|_| )
val output : Expression
active recognizer TermWithTerm: (Operation -> bool) -> Expression -> Expression option

Full name: fs.( |TermWithTerm|_| )
val left : Expression
val right : Expression
val i : int
val randomExpression : min:int -> max:int -> length:int -> Expression

Full name: fs.randomExpression
val length : int
val display : _arg1:Expression -> string

Full name: fs.display
Int32.ToString() : string
Int32.ToString(provider: IFormatProvider) : string
Int32.ToString(format: string) : string
Int32.ToString(format: string, provider: IFormatProvider) : string
val i : Expression
val op : Operation
val exp : Expression
Multiple items
type String =
  new : value:char -> string + 7 overloads
  member Chars : int -> char
  member Clone : unit -> obj
  member CompareTo : value:obj -> int + 1 overload
  member Contains : value:string -> bool
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EndsWith : value:string -> bool + 2 overloads
  member Equals : obj:obj -> bool + 2 overloads
  member GetEnumerator : unit -> CharEnumerator
  member GetHashCode : unit -> int
  ...

Full name: System.String

--------------------
String(value: nativeptr<char>) : unit
String(value: nativeptr<sbyte>) : unit
String(value: char []) : unit
String(c: char, count: int) : unit
String(value: nativeptr<char>, startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int) : unit
String(value: char [], startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int, enc: Text.Encoding) : unit
String.Format(format: string, [<ParamArray>] args: obj []) : string
String.Format(format: string, arg0: obj) : string
String.Format(provider: IFormatProvider, format: string, [<ParamArray>] args: obj []) : string
String.Format(format: string, arg0: obj, arg1: obj) : string
String.Format(format: string, arg0: obj, arg1: obj, arg2: obj) : string
val eval : e:Expression -> Expression

Full name: fs.eval
val e : Expression
val fold : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

Full name: Microsoft.FSharp.Collections.List.fold
Multiple items
type TestAttribute =
  inherit Attribute
  new : unit -> TestAttribute
  member Description : string with get, set

Full name: NUnit.Framework.TestAttribute

--------------------
TestAttribute() : unit
val arithmeticTest : unit -> unit

Full name: fs.arithmeticTest
val dt : DataTable
Multiple items
type DataTable =
  inherit MarshalByValueComponent
  new : unit -> DataTable + 2 overloads
  member AcceptChanges : unit -> unit
  member BeginInit : unit -> unit
  member BeginLoadData : unit -> unit
  member CaseSensitive : bool with get, set
  member ChildRelations : DataRelationCollection
  member Clear : unit -> unit
  member Clone : unit -> DataTable
  member Columns : DataColumnCollection
  member Compute : expression:string * filter:string -> obj
  ...

Full name: System.Data.DataTable

--------------------
DataTable() : unit
DataTable(tableName: string) : unit
DataTable(tableName: string, tableNamespace: string) : unit
val randomExpr : Expression
val validationResult : int
DataTable.Compute(expression: string, filter: string) : obj
type Convert =
  static val DBNull : obj
  static member ChangeType : value:obj * typeCode:TypeCode -> obj + 3 overloads
  static member FromBase64CharArray : inArray:char[] * offset:int * length:int -> byte[]
  static member FromBase64String : s:string -> byte[]
  static member GetTypeCode : value:obj -> TypeCode
  static member IsDBNull : value:obj -> bool
  static member ToBase64CharArray : inArray:byte[] * offsetIn:int * length:int * outArray:char[] * offsetOut:int -> int + 1 overload
  static member ToBase64String : inArray:byte[] -> string + 3 overloads
  static member ToBoolean : value:obj -> bool + 17 overloads
  static member ToByte : value:obj -> byte + 18 overloads
  ...

Full name: System.Convert
Convert.ToInt32(value: DateTime) : int
   (+0 other overloads)
Convert.ToInt32(value: string) : int
   (+0 other overloads)
Convert.ToInt32(value: decimal) : int
   (+0 other overloads)
Convert.ToInt32(value: float) : int
   (+0 other overloads)
Convert.ToInt32(value: float32) : int
   (+0 other overloads)
Convert.ToInt32(value: uint64) : int
   (+0 other overloads)
Convert.ToInt32(value: int64) : int
   (+0 other overloads)
Convert.ToInt32(value: int) : int
   (+0 other overloads)
Convert.ToInt32(value: uint32) : int
   (+0 other overloads)
Convert.ToInt32(value: uint16) : int
   (+0 other overloads)
val result : Expression
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val x : int
val should : f:('a -> #Constraints.Constraint) -> x:'a -> y:obj -> unit

Full name: FsUnit.TopLevelOperators.should
val equal : x:'a -> EqualsConstraint

Full name: FsUnit.TopLevelOperators.equal
Raw view Test code New version

More information

Link:http://fssnip.net/jy
Posted:11 years ago
Author:devshorts
Tags: expression tree , arithmetic