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.

Algorithm

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()))
}

Function definitions

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 },
    }
}

REPL and finalized calculator

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.