带有用于遍历树结构的模板的访客模式

Visitor Pattern with templates for traversing tree structure

提问人:Jacob 提问时间:7/12/2023 最后编辑:marc_sJacob 更新时间:7/30/2023 访问量:115

问:

我得到了一个类似“树”的结构,它表示一个简单的加法表达式。(例 2 + 4 + (3 + 5))

我正在使用访客模式遍历树并找到总和。问题是我希望我的实现使用模板,这会导致一些奇怪的错误。

我需要每个子表达式的 accept 函数能够返回任何类型,以便我可以执行的不仅仅是整数运算

#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;
}

错误:函数模板声明中不允许使用“virtual” (对于 Expr::accept)

C++ 抽象语法树 访客模式

评论

0赞 Jacob 7/12/2023
还有其他堆栈溢出问题与我遇到的问题基本相同,但这些问题很复杂,我试图理解它们但无济于事
0赞 user4581301 7/12/2023
更好的错误消息:godbolt.org/z/jK1MzrTbf
0赞 user4581301 7/12/2023
簿记(通常是 V 表)必须有多大才能支持无限数量的可能实例化?
0赞 Jacob 7/12/2023
错误消息不是他们的问题,而是设计。有没有其他方法可以实现这一点?
1赞 Jacob 7/12/2023
有用的链接: codeproject.com/Tips/1018315/Visitor-with-the-Return-Value

答:

0赞 jpalecek 7/30/2023 #1

解决此问题的一种方法是删除返回值并将结果保留在访问者中。这样就变成了Visitor<T>

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

Adder也将删除返回值,并添加结果字段

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 ...

并且还将删除其模板参数。然后,您必须从实例中提取结果。Expr::acceptmainAdder<int>