Visitor Pattern with templates for traversing tree structure

Question

I got a "tree" like structure that represents a simple addition expression. (ex 2 + 4 + (3 + 5))

I'm using the visitor pattern to traverse the tree and find the sum. The problem is that I want my implementation to use templates which causes some weird errors.

I need the accept function of each of the child expressions to be able to return any type so that I can perform more than just integer operations

#include <iostream>
#include <vector>

#define print(x) std::cout << x << "\n"; 

class Add;
class Number;

// Basic template for visitor class

template <class T>
class Visitor {
public:
    virtual T visitAdd(Add* add) = 0;
    virtual T visitNumber(Number* num) = 0;
};

// Visitor made for adding

template <class T>
class Adder : public Visitor<T> {
public:
    T visitAdd(Add* add) override;
    T visitNumber(Number* num) override;
};

// Node types for expression tree

class Expr {
public:
    template <class T>
    virtual T accept(Visitor<T>* visitor) = 0;
};

class Add : public Expr {
public:
    Expr* left;
    Expr* right;

    Add(Expr* left, Expr* right) : left(left), right(right) {};

    template <class T>
    T accept(Visitor<T>* visitor) {
        return visitor->visitAdd(this);
    }
};

class Number : public Expr {
public:
    int value;

    Number(int value) : value(value) {};

    template <class T>
    T accept(Visitor<T>* visitor) {
        return visitor->visitNumber(this);
    }
};

template <class T>
T Adder<T>::visitAdd(Add* add) {
    return add->left->accept(this) + add->right->accept(this);
}

template <class T>
T Adder<T>::visitNumber(Number* num) {
    return num->value;
}

int main() {

    // Should represent (5 + 2) + (7 + (4 + 2))
    Expr* expression = new Add(
        new Add(
            new Number(5),
            new Number(2)
        ),
        new Add(
            new Number(7),
            new Add(
                new Number(4),
                new Number(2)
            )
        )
    );

    // Print sum as int
    Adder<int> intAdder = Adder<int>();
    print(expression->accept(&intAdder));

    // Print sum as float
    Adder<float> floatAdder = Adder<float>();
    print(expression->accept(&floatAdder));

    return 0;
}

Error: 'virtual' is not allowed in a function template declaration (for Expr::accept)

Answer 1

One way to solve it is drop the return value and retain the result inside the visitor. That way Visitor<T> becomes

struct Visitor {
    virtual void visitAdd(Add* add) = 0;
};

Adder will drop the return value as well, and add the result field

template <class T>
struct Adder : public Visitor<T> {
    void visitAdd(Add* add) override { 
      add->left->accept(this);
      add->right->accept(this); }
... left as an exercise for the reader ...

and Expr::accept will drop its template parameter as well. In main you then have to extract the result from the Adder<int> instance.