MarginalHacks.com DaveSource.com
libExpr
 

What is it?

This is a ruby library that can convert string expressions with variables to RPN or Prefix or AST (abstract syntax tree) for quick evaluation.

That means you can give it something like (as a string):

  "12   3*6 / -(14 3) ^ 2 ^ 3"

And it will convert it to an RPN or Prefix or AST expression object, and then you can evaluate it. (Default is AST) This is as simple as:

require 'libExpr'
exprObj = Expr.new("12   3*6 / -(14 3) ^ 2 ^ 3")
answer = exprObj.eval() 
# Or, if you don't need to repeat the evaluation:
answer = Expr.new("12   3*6 / -(14 3) ^ 2 ^ 3").eval()

That in itself might not be interesting, since you can always use the built-in language eval() (although this one doesn't require any sanitizing of inputs to avoid the inherent security dangers that 'eval()' has).

You can also supply it with expressions that have variables:

  "12   someVar * 6 / (32 - anotherVar)"

And when you evaluate the expression object you can supply a block which the evaluator will use to get any variables, such as:

vars['foo'] = 42
vars['bar'] = 3
require 'libExpr'
someExpr = Expr.new("5*foo-6/bar")
answer = someExpr.eval() { |varname| vars[varname] }
# Returns  5*42-6/3 = 208

# And evaluate again with different vars
vars['foo'] = 100
answer = someExpr.eval() { |varname| vars[varname] }
# Now returns 5*100-6/3 = 498
When you create the expression object, you can even supply the regexp that it will use to determine what constitutes a variable/label, which can be useful if your variable may otherwise get confused with operations, such as a project where all my variables were of the form "%VARIABLENAME" - which otherwise would look like the '%' op preceding a 'VARIABLENAME'. It's the second arg to the constructor. You can even implement some simple external function calls this way. Anything that a ruby block can calculate.

This can be useful when:

  1. Eval is not safe (no need to sanitize inputs here)
  2. 'Variable' evaluation is different from ruby variables
  3. Expressions are evaluated many times with different variable values
  4. 'Variables' may not actually be normal variable notation. I.e.: [`PARAMS@SOME_VAL("DEFAULT")]
Eval is fairly fast - runs about 50% of the speed of an actual ruby eval().

This is done with a modified Shunting-Yard Algorithm that can handle Unary/Ternary operations and short-circuiting of operations, so it's also potentially interesting to anyone trying to implement Shunting-Yard for their own application.

Unary Ops?

Yes - Dijkstra's original Shunting-Yard algorithm could only handle binary operations (operations that take two operands). To confuse the issue further, unary operations (such as '-a' and ' a') also have binary counterparts (such as 'a-b' and 'a b'). Two changes are needed to handle unary ops:
  1. A different operator needs to be used for the unary op vs the binary op. Since libExpr has operator objects, it's easy to create two different objects, and I used a key for hashing ops where a unary op has a space before it, i.e. " -" for unary negative and "-" for binary subtraction.
  2. To recognize unary '-' as opposed to binary '-' is actually pretty simple when we realize that a unary '-' unambiguously will always follow either a left paren '(' or another operator (such as '3 -7'). In all other cases it is a binary subtraction. Once we see that, we can just save the last token we saw when we run the Shunting-Yard, and that can tell us whether it's a unary or binary op (if the token supports both)
  3. As a final point, when it's a unary op, we obviously only push one operand instead of two.
Handling ternary ops (?:) was very similar, except that we don't treat the ':' as an actual operation, we throw it away after ensuring (as a sanity check) that it exists to separate the second and third operands, then we just push all three operands.

Finally, short circuiting was only added for AST, because for an AST it's trivial to simply not traverse one side of the tree. It would be interesting to write an algorithm that would intelligently throw out the proper number of operators/operands from an RPN or Prefix stack to accomplish short circuiting, but that's when my development on this project stopped. Use AST if you need short-circuiting.

Last of all, I also added an 'if-then' operator "a -> b" which is effectively logically equivalent to "!a || b". I added this simply because I needed it for a project I was working on.

Format Capabilities

Format Unary ops ( a, -a) Short-Circuit (||,&&,?:) Ternary-Ops (?:)
RPN Yes No No
Prefix Yes Yes No
AST Yes Yes Yes

Format Info

RPN (Reverse Polish Notation aka "postfix"):
Fastest (slightly), simplest to view and debug, but missing short-circuit/ternary
Prefix
Converts to RPN then quick conversion to Prefix. Supports short-circuit (for &&,||)
AST
Can do ternary ops. Also fast, though harder to debug/understand since it's a tree

Notes about short-circuit

Since there aren't function calls (although you could arguably implement them with the variables) then the short-circuiting mostly will only effect performance (by doing unnecessary calculations), but there are also cases such as:
  (a == 0) || (num/a)
Which will incorrectly cause a ZeroDivisionError if you don't have short-circuit turned on.

Testing

There is a testbench included with the library that is somewhat interesting. It generates a large mass of random legal expressions that are mathematical expressions (such as "3 7*-4") as well as logical expressions (such as "(3 < 12) || (9==5 4)") or a mix of both, such as "(4 < 17) ? (8 1) : (9/12-3)", except generally far more complicated than these examples. It then compares the three expression systems to ruby eval() and ensures that everything is calculated correctly. It also creates a few variables to test variable evaluation as well. Definitely useful if you want to add anything to the expression library.

An example expression

-  1-3   (- var[:n2])    ( (var[:t1] )   ?  (var[:n2])   :- 1)  ^  (  ( - ( var[:n0] ) ) * 10 &((var[:f1] ) ? var[:n2]  : ( - (10) % ( var[:n0] )  )* var[:n2] ) ) 
Which correctly gives us the answer -4

License:

This software is essentially free, but feel free to read my payment spiel
Please read the full license

Documentation?

There's more docs inside the source, take a look at the commenting.

Download:

You can get the ruby source directly, as well as the testbench, or just get the tar.gz.

Back

MarginalHacks.com