README
¶
go-meval
A mathematical expression parser / evaluator in go.
It uses simply the shutting yard algorithm to parse a mathemical expression in an AST.
This AST can then be evaluated within a context, letting user define a dictionnary of expression that can refer other expression. It is not designed to be fast, but only to provide an easy way to mathematically parametrize your program at a configuration level.
1. Installation
go get github.com/atuleu/go-meval
2. Roadmap
Still in alpha release. No complex github issue for that task list
see roadmap
3. Contribute
Documentation
¶
Overview ¶
Package meval provides a mathematical expresison parser. It can parse mathematical expresison into an AST and evaluate it. It also support the concept of variable through Context : An Expression can refer any other expression defined in a Context. For simple case use, a nil Context could be used (any expression refering another expression will fail at evaluation).
Basics ¶
An expression can be parsed using Compile, and evaluated with a nil context. See #Expression basic example.
Context ¶
One can use context, in order for your expression to refer to others, aka variable.
TODO(tuleu): document a context and how to use it
TODO(tuleu) package global example
Index ¶
- func MustRegisterOperator(opToken string, precedence int, leftAssociative bool, evaluer NEvaluer)
- func RegisterFunction(name string, cardinality uint, evaluer NEvaluer)
- func RegisterOperator(opToken string, precedence int, leftAssociative bool, evaluer NEvaluer) error
- type CallStack
- type Context
- type Expression
- type Lexer
- type MapContext
- type NEvaluer
- type Token
- type TokenType
- Bugs
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func MustRegisterOperator ¶
func RegisterFunction ¶
RegisterFunction register a new function with the given cardinality. The list of float passed to the evaluer function is asserted to be cardinatily
Types ¶
type CallStack ¶
type CallStack struct {
// contains filtered or unexported fields
}
CallStack is meant to be embedded in any type that want to implement Context
type Context ¶
type Context interface {
// Returns an expression from a given name.
GetExpression(string) (Expression, error)
// contains filtered or unexported methods
}
A Context is a kind of dictionnary of expression. You can pass it to Eval.
type Expression ¶
type Expression interface {
// Evaluates The expression. You can pass a context to refer other
// expression. You can also pass nil as a context.
Eval(Context) (float64, error)
}
Expression can be evaluated to float from a Context
BUG(tuleu): the expression evaluation mechanism is so simple that call loop can be easily implemented !
Example (Basic) ¶
package main
import (
"fmt"
"math"
. "gopkg.in/check.v1"
)
type ExprSuite struct {
c *MapContext
}
var _ = Suite(&ExprSuite{
c: NewMapContext(),
})
type ExpResult struct {
Result float64
Input string
}
func (e ExpResult) String() string {
return fmt.Sprintf(" %s == %f", e.Input, e.Result)
}
func (s *ExprSuite) SetUpSuite(c *C) {
err := s.c.CompileAndAdd("foo", "3.0")
c.Assert(err, IsNil, Commentf("Got error at SetUp: %s", err))
}
func (s *ExprSuite) TestBasicEval(c *C) {
exps := []ExpResult{
{0.0, "0.00"},
{4.0, "1.0 + 2.0 + 1.0"},
{1.12345, "1.12345"},
{11.0, "1.0 + 10.0"},
{1 / 10.0, "1.0 / 10.0"},
{30.0, "3.0 * 10.0"},
{-2.0, "8.0 - 10.0"},
{9.0, "3 * foo"},
{27.0, "3 ^ 3 ^1"},
{math.Pow(math.Cos(42.0)*3.14159+2, 2.45), "( cos(42.0) * 3.14159 + 2 ) ^2.45"},
{0.0, "sin(0.0)"},
{0.0, "asin(0.0)"},
{1.0, "cos(0.0)"},
{0.0, "acos(1.0)"},
{0.0, "tan(0.0)"},
{0.0, "atan(0.0)"},
{0.0, "sqrt(0.0)"},
{math.Exp(0.0), "exp(0.0)"},
{0.0, "ln(1.0)"},
{1.0, "log(10.0)"},
{2.0, "ceil(1.5)"},
{1.0, "floor(1.5)"},
{math.Pi / 4, "atan2(1.0,1.0)"},
{math.Pi / 4, "pi() / 4"},
}
for i, e := range exps {
ee, err := Compile(e.Input)
if c.Check(err, IsNil, Commentf("[%d: %s]: got error at compilation : %s", i, e, err)) == false {
continue
}
res, err := ee.Eval(s.c)
if c.Check(err, IsNil, Commentf("[%d: %s]: got error at evaluation: %s", i, e, err)) == false {
continue
}
c.Check(res, Equals, e.Result)
}
}
func (s *ExprSuite) TestUnfoundVariableEvaluation(c *C) {
exp, err := Compile("1.0 * does * not + exist")
c.Assert(err, IsNil)
res, err := exp.Eval(s.c)
c.Assert(err, Not(IsNil))
c.Check(err.Error(), Equals, "Could not find 'does' in MapContext")
c.Check(math.IsNaN(res), Equals, true)
res, err = exp.Eval(nil)
c.Assert(err, Not(IsNil))
c.Check(err.Error(), Equals, "'does' referenced, but no Context providen")
c.Check(math.IsNaN(res), Equals, true)
}
func (s *ExprSuite) TestCyclicEvaluationNotPermitted(c *C) {
//create a cycle of references
s.c.CompileAndAdd("bar", "sqrt(baz)")
s.c.CompileAndAdd("baz", "foobar * foobar")
s.c.CompileAndAdd("foobar", "bar ^ 2.0")
//we should clean in any case
defer func() {
s.c.Delete("bar")
s.c.Delete("baz")
s.c.Delete("foobar")
}()
exp, err := Compile("bar + 42.0")
c.Assert(err, IsNil, Commentf("Got compilation error %s", err))
res, err := exp.Eval(s.c)
c.Assert(err, Not(IsNil))
c.Check(err.Error(), Equals, "Got cyclic dependency bar -> baz -> foobar -> bar")
c.Check(math.IsNaN(res), Equals, true)
}
type CompileError struct {
input, error string
}
func (s *ExprSuite) TestCompilationError(c *C) {
// this is for internal stuff
err := registerOpToken("%", TokPlus+100)
c.Assert(err, IsNil)
tests := []CompileError{
{"( 2.0 ))", "Mismatched parenthese in ( 2.0 ))"},
{"(( foo )", "Mismatched parenthese in (( foo )"},
{"( +0x ))", "Bad number syntax \"+0x\""},
{"( +0x ))", "Bad number syntax \"+0x\""},
{"sin(0.0),", "Misplaced comma or mismatched parenthese in sin(0.0),"},
{"atan2(0.0 +,2.1)", "Evaluation stack error for '+', need 2 element, but only 1 provided"},
{"sin(0.0 , 0.3)", "Evaluation stack error, still got 2 element instead of 1 at the final state"},
{"5 % 3", "Operator '%' is not yet implemented"},
{"5 + ", "Evaluation stack error for '+', need 2 element, but only 1 provided"},
{"sin()", "Evaluation stack error for 'sin()', need 1 element, but only 0 provided"},
{"(5 + )", "Evaluation stack error for '+', need 2 element, but only 1 provided"},
{" * 3 + 2", "Evaluation stack error for '*', need 2 element, but only 1 provided"},
{" + 2 + 3", "Evaluation stack error for '+', need 2 element, but only 1 provided"},
}
for i, t := range tests {
_, err := Compile(t.input)
if c.Check(err, Not(IsNil)) == false {
continue
}
c.Check(err.Error(), Equals, t.error, Commentf("[%d] : %s]", i, t.input))
}
}
func main() {
expr, err := Compile("1.0 + 2.0")
if err != nil {
fmt.Printf("Got error: %s", err)
return
}
res, err := expr.Eval(nil)
if err != nil {
fmt.Printf("Got error: %s", err)
return
}
fmt.Printf("%f", res)
}
type FunctionAndResult struct {
input string
result float64
}
func (s *ExprSuite) TestCanGenerateRandom(c *C) {
e, err := Compile("rand()")
c.Assert(err, IsNil, Commentf("Got compilation error %s", err))
res, err := e.Eval(nil)
c.Assert(err, IsNil, Commentf("Got evaluation error %s", err))
c.Check(res >= 0, Equals, true)
c.Check(res < 1, Equals, true)
}
// Theses tests are more for internal check coverage
func (s *ExprSuite) TestBadASTError(c *C) {
//This is more an internal error, so we modify an existing AST to
//add a new argument to a nExp
e, err := Compile("sin(1.0)")
c.Assert(err, IsNil)
ee, ok := e.(*nExp)
c.Assert(ok, Equals, true, Commentf("A function is evaluated as an nExp"))
ee.children = append(ee.children, &valueExp{3.0})
_, err = e.Eval(nil)
c.Assert(err, Not(IsNil))
c.Check(err.Error(), Equals, "Bad AST, expression expected 1 children, got 2")
}
// This a know bug, the lexer returns a valid hexadecimal number, that
// cannot be parsed as a float
func (s *ExprSuite) TestBug_BadStrconvError(c *C) {
//Normallly all parsed number shouldbe able to be parsed by strconv
badNumbers := []string{
"0x12",
"0b001",
"0XAB",
"0B11001",
}
for _, n := range badNumbers {
_, err := Compile(n)
c.Assert(err, Not(IsNil))
c.Check(err.Error(), Equals, "Internal Lexer error. Lexer gave us value "+n+", but strconv.Float64 cannot convert it : strconv.ParseFloat: parsing \""+n+"\": invalid syntax")
}
}
func (s *ExprSuite) TestCanRegisterOperator(c *C) {
err := RegisterOperator("<", 10, false, func(a []float64) float64 {
if a[0] < a[1] {
return 1.0
}
return 0.0
})
c.Assert(err, IsNil)
defer delete(operators, tokUserStart)
err = RegisterOperator(">", 10, false, func(a []float64) float64 {
if a[0] > a[1] {
return 1.0
}
return 0.0
})
c.Assert(err, IsNil)
defer delete(operators, tokUserStart+1)
// Here the precedence should make sure that - is popped out
e, err := Compile("1.0 - 0.6 < 0.5")
c.Assert(err, IsNil)
res, err := e.Eval(nil)
c.Assert(err, IsNil)
c.Check(res, Equals, 1.0)
err = RegisterOperator(">a", 10, false, func(a []float64) float64 { return 0 })
c.Assert(err, Not(IsNil))
c.Check(err.Error(), Equals, "Invalid operator syntax \">a\"")
didPanic := false
defer func() {
if r := recover(); r != nil {
didPanic = true
}
c.Check(didPanic, Equals, true)
}()
MustRegisterOperator(">a", 10, false, func(a []float64) float64 { return 0 })
}
Output: 3.000000
func Compile ¶
func Compile(input string) (Expression, error)
Compile a new expression from an input string
type Lexer ¶
type Lexer struct {
// contains filtered or unexported fields
}
A Lexer is used to sequentially cut an input string in a sequence of Token.
A new Lexer can be instantiated using NewLexer(). Each token would be obtain using Lexer.Next().
type MapContext ¶
type MapContext struct {
// In order to be a Context, one should embed a CallStack
CallStack
// contains filtered or unexported fields
}
MapContext represents the most simple context, aka a dictionnary of expressions.
func (*MapContext) Add ¶
func (c *MapContext) Add(name string, e Expression)
Add adds a new expression to the MapContext
func (*MapContext) CompileAndAdd ¶
func (c *MapContext) CompileAndAdd(name, input string) error
CompileAndAdd compiles and adds a new expression to the MapContext.
It returns the same errors than Compile()
func (*MapContext) Delete ¶
func (c *MapContext) Delete(name string)
Delete deletes the given expression from the MapContext if it exists.
func (*MapContext) GetExpression ¶
func (c *MapContext) GetExpression(name string) (Expression, error)
GetExpression returns an Expression storred in the MapContext, or nil
type Token ¶
A Token represent a lexed string
TODO(tuleu): Maybe improve by giving indexes of the input string, and ref to the input string. Value then should be a function
type TokenType ¶
type TokenType int
TokenType represent the type of a Token
const ( // TokPlus is a '+' sign TokPlus TokenType = iota // TokMinus is a '-' sign TokMinus // TokMult is a '*' sign TokMult // TokDivide is a '/' sign TokDivide // TokPower is a '^' TokPower // TokOParen is a '(' sign TokOParen // TokCParen is a ')' sign TokCParen // TokComma is a ',' TokComma // TokIdent is a '[a-zA-Z0-9_]+ regex TokIdent // TokValue is a a floating number value TokValue )
Notes ¶
Bugs ¶
the expression evaluation mechanism is so simple that call loop can be easily implemented !
Source Files