71
loading...
AST Evaluator - Expression calculator
When input text was tokenized, parsed and converted into Abstract Syntax Tree, we can finally get real value out of it. The last step of creation a custom expression calculator.
🇨🇿 V češtině si lze článek přečíst na kutac.cz
The output of the parser, described in the previous article, is Abstract Syntax Tree, or AST. To get a real numeric result, we need to evaluate this tree with a Depth-first search algorithm with post-order ordering. Meaning the whole tree is traversed recursively and each node is evaluated after the whole sub-tree or sub-trees are evaluated.
🔗 The whole code can be found on GitHub in arxeiss/go-expression-calculator repository.
In the first place, leaf nodes are evaluated. They are mostly numeric nodes or variables. And the last node to evaluate is the root of the tree. Which is the operation with the lowest priority. This is exactly, how the parser built the tree.
type FunctionHandler func(x ...float64) (float64, error)
type NumericEvaluator struct {
variables map[string]float64
functions map[string]FunctionHandler
}
func (e *NumericEvaluator) Eval(rootNode ast.Node) (float64, error) {
switch n := rootNode.(type) {
case *ast.BinaryNode:
return e.handleBinary(n)
case *ast.UnaryNode:
return e.handleUnary(n)
case *ast.FunctionNode:
f, has := e.functions[n.Name()]
if !has {
return 0, EvalError(n.GetToken(), fmt.Errorf("undefined function '%s'", n.Name()))
}
// First evaluate sub-tree, current implementation supports only functions with single argument
v, err := e.Eval(n.Param())
if err != nil {
return 0, err
}
// When value from sub-tree is received, call node function
return f(v)
case *ast.VariableNode:
// If variable exists, just return its value
if v, has := e.variables[n.Name()]; has {
return v, nil
}
return 0, EvalError(n.GetToken(), fmt.Errorf("undefined variable '%s'", n.Name()))
case *ast.NumericNode:
// Numeric node is easy, just return value
return n.Value(), nil
}
return 0, EvalError(rootNode.GetToken(), fmt.Errorf("unimplemented node type %T", e))
}
func (e *NumericEvaluator) handleUnary(n *ast.UnaryNode) (float64, error) {
// First evaluate next node, unary has always only one following
val, err := e.Eval(n.Next())
if err != nil {
return 0, err
}
// When value from sub-tree is received, do node operation
switch n.Operator() {
case ast.Substraction:
return -val, nil
case ast.Addition:
return val, nil
}
return 0, EvalError(n.GetToken(), errors.New("unary node supports only Addition and Substraction operator"))
}
func (e *NumericEvaluator) handleBinary(n *ast.BinaryNode) (float64, error) {
// First evaluate left and right subtree
l, err := e.Eval(n.Left())
if err != nil {
return 0, err
}
r, err := e.Eval(n.Right())
if err != nil {
return 0, err
}
// When values from both sub-trees are received, do node operation
switch n.Operator() {
case ast.Addition:
return l + r, nil
case ast.Substraction:
return l - r, nil
case ast.Multiplication:
return l * r, nil
case ast.Division:
return l / r, nil
case ast.FloorDiv:
return math.Floor(l / r), nil
case ast.Exponent:
return math.Pow(l, r), nil
case ast.Modulus:
return math.Mod(l, r), nil
}
return 0, EvalError(n.GetToken(), fmt.Errorf("unimplemented operator %s", n.Operator()))
}When creating a new numeric evaluator
eval := &NumericEvaluator{} it is possible to specify custom functions, which can be used then in expressions. Parser currently supports only functions with 1 argument, but that will be extended in the future as well. For now, there are some functions prepared in evaluator.MathFunctions().func MathFunctions() map[string]FunctionHandler {
// This is only part of all prepared functions
return map[string]FunctionHandler{
"Abs": func(x ...float64) (float64, error) { return math.Abs(x[0]), nil },
"Ceil": func(x ...float64) (float64, error) { return math.Ceil(x[0]), nil },
"Floor": func(x ...float64) (float64, error) { return math.Floor(x[0]), nil },
"Sin": func(x ...float64) (float64, error) { return math.Sin(x[0]), nil },
"Sqrt": func(x ...float64) (float64, error) { return math.Sqrt(x[0]), nil },
}
}The whole calculator is available as Read-Eval-Print Loop or REPL. Just follow the README in github.com/arxeiss/go-expression-calculator repository. In the future, I would like to improve the console and integrate Go Prompt library.
71