bet
A Binary Expression Tree implementation which can evaluate infix mathematical expressions
npm install bet
Want to see pretty graphs? Log in now!
1 | downloads in the last day |
33 | downloads in the last week |
125 | downloads in the last month |
Last Published By | |
---|---|
Version | 0.2.0 last updated a year ago |
Keywords | binary, expression, tree, shunting, yard |
Repository | https://github.com/paulmoore/BET (git) |
Dependencies | None |
Dependents | pimatic |
A Mathematical Evaluator for CoffeeScript and JavaScript
This project makes use of Binary Expression Trees and the Shunting-Yard algorithm to evaluate infix equations and produce a numerical result.
http://paulmoore.mit-license.org
Installing
Typical NPM installation:
npm install bet
Usage
The library expects that you have some way of separating your tokens, whether it is a string.split
, or something more involved, is up to you.
Simple Example
In CoffeeScript
# Require the module
{evaluate} = require 'bet'
# Evaluating an equation
evaluate ['1','+','isqrt','(','2','^2',')'], (error, result) ->
console.log error ? result
In JavaScript
// Require the module
var BET = require("bet");
// Evaluating an equation
BET.evaluate(['1','+','isqrt','(','2','^2',')'], function(error, result) {
if (error !== null) {
console.log(error);
} else {
console.log(result);
}
});
There is also a synchronous method
{evaluateSync} = require 'bet'
try
val = evaluateSync [1, '+', 2]
console.log val
# throws an error
evaluateSync ['*', '+', 1, 'x']
catch e
console.log e
You will want to check the source to see the full list of built-in operators and functions that are currently supported.
Custom Operators
You can define or redefine operators as you wish.
{evaluate, operators} = require 'bet'
# C style logical AND
operators['&&'] =
assoc: 'left'
prec: 0
argc: 2
fix: 'in'
exec: (args) -> 1 if args[0] isnt 0 and args[1] isnt 0 else 0
evaluate [1,'&&',1,'&&',0], (error, result) ->
console.log error ? result
Operators require the following attributes:
assoc: Associativity ['left' or 'right'] Associativity indicates the order in which operators of the same precedence are executed. For instance,
&&
has an associativity of 'left' and thusa && b && c
is evaluated as(a && b) && c
.prec: Precedence [integer] Operators with a higher precedence (higher value) are executed first. For instance,
1 + 2 * 3
is evaluated as1 + (2 * 3)
.argc: Argument count [integer] The number of numerical operands an operator needs to execute. In practice this is usually only 1 (for unary) or 2 (for binary) operators. For instance,
+
requires 2 operands e.g.1 + 2
, whereas1 +
will produce an error.fix: How the operator is 'fixed' ['in', 'pre', or 'post'] Most binary operators are infixed, meaning the operator is between the operands e.g.
1 / 2
. Unary operators are usually either pre or post fixed, e.g.5 !
(postfixed) ornot 1
(prefixed). However, you can also have infixed unary operators (just be careful with associativity!) such as pre and post increment/decrement, e.g.++1
and1++
are both valid.exec: Evaluator [function] This is the function that is called to evaluate the operator. It is given a single argument as an array, with length argc. All values are numerical.
Custom Functions
Functions are similar to operators. You can also define new or redefine functions. Functions in this library are invoked C style fn(arg1,arg2,arg3)
. Currently, variable argument functions are not supported. Function arguments can be expressions in themselves. Functions cannot have the same name as an operator.
{evaluate, functions} = require 'bet'
# Averages 3 numbers
functions['avg'] =
argc: 3
exec: (args) -> (args[0] + args[1] + args[2]) / 3
evaluate ['avg','(',1,2,3,')'], (error, result) ->
console.log error ? result
Declaration of a function is much like an operator. However it requires only 2 attributes:
argc: Argument count [integer] The number or arguments the function takes.
exec: Evaluator [function] This is the function that is called to evaluate the function. It is passed an array of in order numerical arguments.
But JavaScript IS a Mathematical Evaluator
Good point. Here is one particular use case that prompted me to write this library:
A Basic Approach
You are writting a game involves players entering equations. You may at first do something like this:
# Spaces are used to separate tokens.
# User enters an equation, we end up with a string like this:
eqn = '1 + 2'
result = eval eqn
doSomethingWith result
This will work, and for most basic math operators will do what you need.
A More Complicated Example
Let's say you don't want to deal with fractions or decimals, you want your operations to have integer only results. So then you may say "Ok, I'll write a preprocessor to Math.floor
division operators"
eqn = '1 + 2 / 3'
# You run it through a parser that produces this:
eqn = '1 + Math.floor(2 / 3)'
# ...
But then the User enters something invalid:
eqn = '1 + 2 3 / 2'
# parse it...
eqn = '1 + 2 Math.floor(3 / 2)'
# errors
Or should it have been?:
eqn = '1 + 2 3 / 2'
# parse it...
eqn = '1 + Math.floor(23 / 2)'
# errors
You also have to watch out for:
eqn = '1 + (3 + 2) / 2'
# parse it...
eqn = '1 + (3 + 2 Math.floor() / 2)'
# errors
Anyways, the problem starts to compound when you need things like:
- Custom operators
- Built-in and user-defined functions
- Associativity, precedence, and argument length control
- Error reporting of what went wrong when an expression does not evaluate
Using Binary Expression Trees to your Advantage
Luckily this problem has been solved long before I was born. The idea is, once you have separated the equation into individual tokens to rearrange them according to their precedence. Then you can the equation, in Reverse Polish Notation, and execute it.
So, if you start with an equation like this:
1 + 2 * 3 + 4 ^ 5
You produce the expression tree in RPN format as follows:
1 2 3 * + 2 3 2 ^ ^ +
Which gives you the correct order of operations, so you can simply execute the equation as a stack if you know how many arguments each operator takes:
> pop
[1]
> pop
[1, 2]
> pop
[1, 2, 3]
> evaluate *
[1, 6]
> evaluate +
[7]
> pop
[7, 2]
> pop
[7, 2, 3]
> pop
[7, 2, 3, 2]
> evaluate ^
[7, 2, 9]
> evaluate ^
[7, 512]
> evaluate +
> [519]
...Or you can find a better explanation of BETs and RPN works here