Baumstruktur - this-Wert zuweisen Alternative

[happystudent]

Hallo,

ich habe, in Anlehnung an das Tutorial hier aus dem Forum, folgenden Code für dynamische Gleichungen:

Vorab: Rohe Pointer und new sind nur der Einfachheit halber für Demonstrationszwecke... ich weiß dass das so nicht gemacht werden sollte.

#include <iostream>

struct Node { 
	virtual double eval() const = 0;
};
struct AddNode : Node  { 
	Node *lhs, *rhs;
	AddNode(Node *lhs, Node *rhs) : lhs(lhs), rhs(rhs) {}
	virtual double eval() const { return lhs->eval() + rhs->eval(); }
};
struct SubNode : Node {
	Node *lhs, *rhs;
	SubNode(Node *lhs, Node *rhs) : lhs(lhs), rhs(rhs) {}
	virtual double eval() const { return lhs->eval() - rhs->eval(); }
};
struct ValNode : Node {
	double value;
	ValNode(double value) : value(value) {}
	virtual double eval() const { return value; }
};

int main()
{
	Node *expression = new AddNode(new ValNode(5), new ValNode(2));
	std::cout << expression->eval() << "\n";
}

Der Code funktioniert soweit: Ich kann Gleichungen erstellen und auswerten.

Jetzt würde ich aber gerne eine Funktion hinzufügen, die z.B. alle " + " in einer Gleichung durch " - " ersetzt - also alle AddNode in einer Gleichung sollen durch SubNode ersetzt werden und zwar möglichst ohne immer den Ganzen Baum kopieren zu müssen. Ich wollte das zuerst wie die eval Funktion implementieren, also als virtuelle, vererbte Member-Funktion.

Problem: Dafür müsste ich ja dem this -Objekt in der Member-Funktion einen neuen Wert zuweisen, was ja nicht möglich ist (da this const ist):

virtual void replace() { this = new SubNode(lhs, rhs); } // In AddNode, geht aber nicht

Wie würde man das gut lösen?

[Mechanics]

Über das Parent Objekt.

[happystudent]

Mechanics schrieb:

Über das Parent Objekt.

Hm, der AddNode hat hier aber gar kein Parent Objekt ( AddNode ist in dem Beispiel ja selbst der Root-Knoten)...

Und selbst wenn ich dann noch eine Art ExprNode als Zwischenschicht einführe, brauche ich doch dann dynamic_cast , um auf die lhs und rhs zugreifen zu können? Das würde ich eigentlich gerne vermeiden...

[Mechanics]

Du willst nicht this austauschen. Du willst dem Node drüber sagen, dass sein lhs jetzt was anderes ist.
Kann man vielleicht über einen Visitor machen.

[happystudent]

Mechanics schrieb:

Du willst nicht this austauschen. Du willst dem Node drüber sagen, dass sein lhs jetzt was anderes ist.
Kann man vielleicht über einen Visitor machen.

Und wie?

Habe das jetzt so versucht umzusetzen:

#include <iostream>

struct ExprNode;
struct AddNode;
struct SubNode;
struct ValNode;

struct Visitor {
	virtual void visit(ExprNode &n) = 0;
	virtual void visit(AddNode &n) = 0;
	virtual void visit(SubNode &n) = 0;
	virtual void visit(ValNode &n) = 0;
};

enum class NodeType {
	Expr,
	Add,
	Sub,
	Val
};
struct Node { 
	virtual double eval() const = 0;
	virtual void accept(Visitor &v) = 0;
	virtual NodeType type() const = 0;
};
struct ExprNode : Node {
	Node *expr;
	ExprNode(Node *expr) : expr(expr) {}
	virtual double eval() const { return expr->eval(); }
	virtual void accept(Visitor &v) { v.visit(*this); }
	virtual NodeType type() const { return NodeType::Expr; }
};
struct AddNode : Node {
	Node *lhs, *rhs;
	AddNode(Node *lhs, Node *rhs) : lhs(lhs), rhs(rhs) {}
	virtual double eval() const { return lhs->eval() + rhs->eval(); }
	virtual void accept(Visitor &v) { v.visit(*this); }
	virtual NodeType type() const { return NodeType::Add; }
};
struct SubNode : Node {
	Node *lhs, *rhs;
	SubNode(Node *lhs, Node *rhs) : lhs(lhs), rhs(rhs) {}
	virtual double eval() const { return lhs->eval() - rhs->eval(); }
	virtual void accept(Visitor &v) { v.visit(*this); }
	virtual NodeType type() const { return NodeType::Sub; }
};
struct ValNode : Node {
	double value;
	ValNode(double value) : value(value) {}
	virtual double eval() const { return value; }
	virtual void accept(Visitor &v) { v.visit(*this); }
	virtual NodeType type() const { return NodeType::Val; }
};

struct ReplaceVisitor : Visitor  {
	virtual void visit(ExprNode &n) { 
		if (n.expr->type() == NodeType::Add) { 
			/* Wie komme ich hier jetzt an n.expr->lhs ohne dynamic_cast? */  
		} 
	}
	virtual void visit(AddNode &n) { /* Selbe hier */ }
	virtual void visit(SubNode &n) { /* Und hier */ }
	virtual void visit(ValNode &n) {}
};

int main()
{
	Node *expression = new ExprNode(new AddNode(new ValNode(5), new ValNode(2)));
	std::cout << expression->eval() << "\n";
	ReplaceVisitor v;
	expression->accept(v);
	std::cout << expression->eval() << "\n";
}

Problem: Auch mit Visitor komme ich nicht an die benötigte Information ran (siehe Kommentar im Code)...

Muss man hier in jedem Objekt auch noch sein Parent speichern? Das will ich vermeiden, weil man dann die Gleichungen ja nicht mehr so einfach hinschreiben kann wie oben in Zeile 68, (Im fertigen Code dann mit Operator-Überladung), zumindest sehe ich nicht, wie.

[Mechanics]

Die visit Funktionen könnten einen Node zurückgeben.

virtual Node visit(const AddNode &n);

[happystudent]

Mechanics schrieb:

Die visit Funktionen könnten einen Node zurückgeben.

virtual Node visit(const AddNode &n);

Verstehe ich nicht...

Wenn ich sowas habe:

struct AddNode : Node {
    // ...
    virtual void accept(Visitor &v) { 
        auto *tmp = v.visit(*this);
        // Was jetzt tun mit tmp?
    }
};

Inwiefern hilft mir dass dann bzw. was soll ich jetzt mit tmp anfangen?

[Mechanics]

Das kriegst schon irgendwie hin Die accept Funktion muss nichts mit dem Rückgabewert anfangen können, der Visitor wird ja auch selber irgendwie aufgerufen, bevor er accept aufruft. Oder, wenn accept von außen aufgerufen wird, dann kann das eben auch den Node zurückgeben.

[Fytch]

Hallo happystudent

Ich hatte 100% genau dasselbe Problem, als ich mit meinem CAS begonnen habe.
Meine Lösung ist sehr ähnlich, wie die von Mechanics beschriebene. Die accept -Memberfunktionen können wahlweise einen unique_ptr zurückgeben. Um diesen Rückgabewert zu verwenden, habe ich eine globale Funktion geschrieben:

template< typename T >
	void Apply( std::unique_ptr< T >& Node, BasicMutableVisitor& Visitor )
	{
		if( auto New = Node->Apply( Visitor ) ) { // oder Node->accept in deinem Fall
			if( !IsType< T >( New.get() ) )
				throw std::logic_error{ "Apply: Visitor has returned an incompatible type" };
			Node = StaticUniquePtrCast< T >( std::move( New ) );
		}
	}

Grundsätzlich wird der Visitor auf den Node angewandt und der Rückgabewert wird, falls vorhanden, in den Node hineingemoved. Bei rekursiven Visitors schreibst du in die accept -Funktion noch Apply( Lhs ) etc. hinein. In meinem Projekt habe ich eine Hierarchie von Visitors, die wahlweise shallow/recursive, mutable/immutable, head-first/tail-first sein können.

Zu deiner anderen Frage "Wie komme ich hier jetzt an n.expr->lhs ohne dynamic_cast?": Wieso nicht einfach static_cast ? Wenn du mit einem enum -Flag schon sichergestellt hast, dass ein Pointer auf einen bestimmten Typ zeigt, dann kannst du dir sicher sein, dass das kein UB erzeugt.

LG

[happystudent]

Fytch schrieb:

Hallo happystudent

Ich hatte 100% genau dasselbe Problem, als ich mit meinem CAS begonnen habe.
Meine Lösung ist sehr ähnlich, wie die von Mechanics beschriebene.

Dachte ich mir doch dass noch mehr Leute dieses Problem haben werden

Habe es inzwischen hinbekommen, hier meine Lösung. Falls jemand noch Verbesserungsvorschläge (außer rohe Pointer/new) auffallen, gerne her damit.

Danke @Fytch und @Mechanics.

#include <iostream>
#include <functional>

struct Node;
struct RootNode;
struct AddNode;
struct SubNode;
struct ValNode;

struct Visitor {
	virtual Node *visit(RootNode &n) = 0;
	virtual Node *visit(AddNode &n) = 0;
	virtual Node *visit(SubNode &n) = 0;
	virtual Node *visit(ValNode &n) = 0;
};

enum class NodeType {
	Root,
	Add,
	Sub,
	Val
};
struct Node { 
	virtual double eval() const = 0;
	virtual Node *accept(Visitor &v) = 0;
	virtual NodeType type() const = 0;
	virtual void iterate_dfs(std::function<void(Node*&)>) = 0;
};
struct RootNode : Node {
	Node *expr;
	RootNode(Node *expr) : expr(expr) {}
	virtual double eval() const { return expr->eval(); }
	virtual Node *accept(Visitor &v) { return v.visit(*this); }
	virtual NodeType type() const { return NodeType::Root; }
	virtual void iterate_dfs(std::function<void(Node*&)> f) { f(expr); expr->iterate_dfs(f); }
};
struct AddNode : Node {
	Node *lhs, *rhs;
	AddNode(Node *lhs, Node *rhs) : lhs(lhs), rhs(rhs) {}
	virtual double eval() const { return lhs->eval() + rhs->eval(); }
	virtual Node *accept(Visitor &v) { return v.visit(*this); }
	virtual NodeType type() const { return NodeType::Add; }
	virtual void iterate_dfs(std::function<void(Node*&)> f) { 
		f(lhs); lhs->iterate_dfs(f); 
		f(rhs); rhs->iterate_dfs(f);
	}
};
struct SubNode : Node {
	Node *lhs, *rhs;
	SubNode(Node *lhs, Node *rhs) : lhs(lhs), rhs(rhs) {}
	virtual double eval() const { return lhs->eval() - rhs->eval(); }
	virtual Node *accept(Visitor &v) { return v.visit(*this); }
	virtual NodeType type() const { return NodeType::Sub; }
	virtual void iterate_dfs(std::function<void(Node*&)> f) {
		f(lhs); lhs->iterate_dfs(f);
		f(rhs); rhs->iterate_dfs(f);
	}
};
struct ValNode : Node {
	double value;
	ValNode(double value) : value(value) {}
	virtual double eval() const { return value; }
	virtual Node *accept(Visitor &v) { return v.visit(*this); }
	virtual NodeType type() const { return NodeType::Val; }
	virtual void iterate_dfs(std::function<void(Node*&)> f) {}
};

template <typename ReplaceNode>
struct ReplaceVisitor : Visitor  {
	virtual Node *visit(RootNode &n) { return nullptr; }
	virtual Node *visit(AddNode &n) { return new ReplaceNode(n.lhs, n.rhs); }
	virtual Node *visit(SubNode &n) { return nullptr; }
	virtual Node *visit(ValNode &n) { return nullptr; }
};

int main()
{
	Node *expression = new RootNode(new AddNode(new ValNode(5), new ValNode(2)));

	std::cout << expression->eval() << "\n";

	ReplaceVisitor<SubNode> v;
	expression->iterate_dfs([&v](Node *&node) {
		if (auto *tmp = node->accept(v)) {
			node = tmp;
		}
	});
	std::cout << expression->eval() << "\n";
}

[Fytch]

Ich würde die Memberfunktionen von Visitor nicht rein virtuell machen, sondern alle implementieren und einfach nullptr zurückgeben lassen.

LG