A Binary Expression Tree implementation which can evaluate infix mathematical expressions
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
Typical NPM installation:
npm install bet
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.
# Require the moduleBET = require 'BET'# Evaluating an equationBET.evaluate ['1','+','isqrt','(','2','^2',')'], (error, result) -> console.log "#{result or error?.toString()}"
You will want to check the source to see the full list of built-in operators and functions that are currently supported.
You can define or redefine operators as you wish.
BET = require 'BET'# C style logical ANDBET.operators['&&'] = assoc: 'left' prec: 0 argc: 2 fix: 'in' exec: (args) -> 1 if args[0] isnt 0 and args[1] isnt 0 else 0
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 thus a && 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 as 1 + (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
, whereas 1 +
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) or not 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
and 1++
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.
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.
BET = require 'BET'# Averages 3 numbersBET.functions['avg'] = argc: 3 exec: (args) -> (args[0] + args[1] + args[2]) / 3
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.
Good point. Here is one particular use case that prompted me to write this library:
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 eqndoSomethingWith result
This will work, and for most basic math operators will do what you need.
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:
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