Evaluator AST - 3. díl vlastní kalkulačky

Article in English can be found on dev.to/arxeiss/ast-evaluator-expression-calculator-1cdg

Tento článek patří do seriálu Vlastní kalkulačka s výrazy. Ostatní články seriálu:

• Lexer - 1. díl vlastní kalkulačky s výrazy
• Shunting yard algoritmus - 2. díl vlastní kalkulačky
• Evaluator AST - 3. díl vlastní kalkulačky
• Recursive descent - 4. díl vlastní kalkulačky

---

Výstupem parseru, popsaného v minulém díle, je Abstraktní syntaktický strom, zkráceně AST. Pro získání číselného výsledku stačí tento strom procházet do hloubky, technikou post-order. Celý strom se prochází rekurzivně a každý uzel je zpracován poté, co je zpracován celý podstrom. 

Algoritmus níže je lehce zjednodušený, implementace včetně spustitelné REPL konzole je opět dostupná na github.com/arxeiss/go-expression-calculator.

Algoritmus

Prvně jsou tedy zpracovány uzly úplně dole ve stromě, naopak naposledy je zpracován kořen stromu. A parser tento strom sestrojil právě tak, aby čísla a proměnné byly listy stromu. Protože mají nejvyšší prioritu. Odspodu nahoru jsou pak uzly s prioritou od nejvyšší po nejmenší. Až kořen stromu má prioritu nejnižší. Nejčastěji tedy sčítání či odčítání, v budoucnu dosazení do proměnné.

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

Přidání a definice funkcí

Při vytváření objektu eval := &NumericEvaluator{} je možné specifikovat vlastní funkce, které pak lze používat ve výrazech. Nyní parser ale podporuje pouze funkce přijímající 1 argument. Pár takových funkcí je připraveno v  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 a hotová kalkulačka

Celá kalkulačka je nyní spustitelná jako Read-Eval-Print Loop, zkráceně REPL. Stačí následovat README v repozitáři github.com/arxeiss/go-expression-calculator. V jednom z dalších kroků bych rád udělal konzoli ještě více interaktivní pomocí knihovny Go Prompt.

V dalším díle bude popsána a přidána druhá metoda parseru, i možnost vytvářet dynamicky proměnné či možnost používat funkce s více parametry.

---

Nápady, postřehy či zkušenosti můžete s ostatními čtenáři sdílet v komentářích