Numberto: Expressions

Numberto has new features!

In previous post I wrote about simple clojure library numberto for experiments with numbers.

New version of numberto has a bunch of new features.

Expressions

Expressions package provides two functions: eval-infix to evaluate infix expression and infix->prefix to build prefix lisp-style expression from mathematical notation.

Let’s give it alias for simplicity

(def e eval-infix)

Evaluate simple math expression

(e "1+2") => 3

or more complex

(e "1+2*(3-4/2)") => 3

handle priorities

(e "2+2*2") => 6

and left/right associativity

(e "1024/2/2/2/2") => 64
(e "2^3^4") => 2417851639229258349412352N

Oh, what’s this? Long numbers? Sure, ratios and floats supported as well

(e "1/3") => 1/3
(e "1.1/0.9") => 1.2222222222222223

Unary operations

(e "(-1)^100") => 1

functions and symbols

(e "sin(e) + sqrt(pi)") => 2.183235141408425

vararg functions

(e "sum(1,2,3,sum())/max(1,2)") => 3

You can also provide bindings for unknown functions and symbols

(e "factorial(n)/20"
   {:bindings
     {"factorial" #(reduce *' (range 1 (inc %)))
      "n" 10}})
=> 181440

Worth to mention that you can easily redefine existing or define your own new unary, binary operations, functions and symbols. Just add additional properties to eval-infix

;; return current time in millis
(e "now()" {:bindings {"now" #(.getTime (java.util.Date.))}}) => some long number
;; override priorities
(e "1+2*3" {:binary-ops {"+" {:function + :priority 100}}}) => 9

infix->prefix has exactly the same functionality, but it builds prefix expression instead.

(infix->prefix "(1+2)*3-(4/avg(3,5)-sum(1))")
=>
"(- (* (+ 1 2) 3) (- (/ 4 (avg 3 5)) (sum 1)))"

It can be useful if you googled some formula but bored to translate it manually to clojure.

For example, take the Simpson’s rule

(infix->prefix "(b-a)/6*(f(a)+4*f((a+b)/2)+f(b))")
=>
"(* (/ (- b a) 6) (+ (+ (f a) (* 4 (f (/ (+ a b) 2)))) (f b)))"

Implementation

Would be good to try instaparse for such purpose, but I decided to use custom implementation using standard Shunting-yard algorithm. Just couple of hacks added to handle unaries and vararg functions. Code is awful. If you really want to dig in - run debug mode.

(binding [*DEBUG* true]
  (e "1+2"))

Limitations

Solvers

Here is the puzzle:

You have four numbers [3, 4, 5, 6].
You have four binary operations [+, -, *, /] and parentheses ()

How to insert operations between numbers to get number 42?

Hah, that simple 3*4 + 5*6 = 42

Ok, get 42, but you forced to use one division /.

Not so obvious?

(solve-insert-ops-num [3 4 5 6] 42) =>
([42N "3+45-6"] [42N "3/4*56"] [42N "3*4+5*6"])

If you use solve-insert-ops function it gives all possible values can be obtained by inserting operations between numbers.

(solve-insert-ops [3 4 5 6]) => ;; long list

Default implementation uses 4 basic operations, no parens and no restrictions. Instead, you can override options

to use parens, specify level

(solve-insert-ops-num [3 4 5 6] 42 {:parens 1}) =>
([42N "3+45-6"] [42N "(3+45)-6"] [42N "3+(45-6)"]
 [42N "3/4*56"] [42N "(3/4)*56"] [42N "3/(4/56)"]
 [42N "3*4+5*6"] [42N "(3*4)+5*6"] [42N "3*4+(5*6)"])

limit some operations

(solve-insert-ops-num [3 4 5 6] 42 {:rules [[:max "*" 1]]}) =>
([42N "3+45-6"] [42N "3/4*56"])

:max, :min, :max-in-a-row, :min-in-a-row options are supported.

Add new operations (supported by expressions package)

(solve-insert-ops-num [3 4 5 6] 80
                      {:ops ["+" "-" "*" "/" "^"]
                       :rules [[:max "^" 1]]}) =>
([80N "3^4+5-6"])

Keep in mind, always limit time consuming operations (like ^) as it builds all possible permutations and you can wait your answer forever.

There are also couple of new interesting things, like getting digits of pi, e, sqrt(n), ratio numbers up to desired level and other. Check it out

mishadoff 29 March 2014
blog comments powered by Disqus