AST Evaluator - Expression calculator
Tags: go, programming, algorithms
Published: 2021-07-01 08:01:45

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](https://www.kutac.cz/pocitace-a-internety/shunting-yard-algoritmus-2-dil-vlastni-kalkulacky) 

--- 

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](https://en.wikipedia.org/wiki/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.

> :link: The whole code can be found on GitHub in [arxeiss/go-expression-calculator](https://github.com/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.

```go
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()`.

```go
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](https://en.wikipedia.org/wiki/Read%E2%80%93eval%E2%80%93print_loop) or **REPL**. Just follow the README in [github.com/arxeiss/go-expression-calculator](https://github.com/arxeiss/go-expression-calculator) repository. In the future, I would like to improve the console and integrate [Go Prompt](https://github.com/c-bata/go-prompt) library.