#include <iostream>
#include <string>

class Leaf;
class TreeNode;

class NodeVisitor {
public:
	void op(Leaf* l);
	void op(TreeNode* t);
};

class Node {
public:
	// tree manipulation
	virtual Node* getLeft() = 0;
	virtual Node* getRight() = 0;
	virtual void setLeft(Node*) = 0;
	virtual void setRight(Node*) = 0;
	
	// tree operations
	virtual void op() = 0;
	virtual int getIntValue() = 0;
	virtual const std::string& getStringValue() = 0;

	virtual void visit(NodeVisitor&) = 0;

	virtual ~Node() {}
};

class TreeNode : public Node {
public:
	TreeNode(const std::string& s = "") : left(0), right(0), value(s) {}

	TreeNode(Node* l, Node* r, const std::string& s = "") : left(l), right(r), value(s) {}

	// tree manipulation
	virtual Node* getLeft() { return left; }
	virtual Node* getRight() { return right; }
	virtual void setLeft(Node* l) { left = l; }
	virtual void setRight(Node* r) { right = r; }

	virtual void visit(NodeVisitor& n) { n.op(this); }

	virtual void op() {
		std::cout << "(";
		if (left)
			left->op();

	  
		std::cout << " " << value << " ";

		if (right)
			right->op();

		std::cout << ")";
	}

	virtual int getIntValue() { return 0; }
	virtual const std::string& getStringValue() { return value; }

	virtual ~TreeNode() {
		if (left)
			delete left;
		if (right)
			delete right;
	}

private:
	std::string value;
	Node* left;
	Node* right;
};

class Leaf : public Node {
public:
	Leaf(int n) : value(n) {}

	// tree manipulation
	virtual Node* getLeft() { return 0; }
	virtual Node* getRight() { return 0; }
	virtual void setLeft(Node*) {}
	virtual void setRight(Node*) {}

	virtual void visit(NodeVisitor& n) { n.op(this); }

	virtual void op() { std::cout << value; }

	virtual int getIntValue() { return value; }
	virtual const std::string& getStringValue() { static std::string s = ""; return s; }

	virtual ~Leaf() {}
private:
	int value;
};

void NodeVisitor::op(Leaf* l) { std::cout << l->getIntValue(); }

void NodeVisitor::op(TreeNode* t) {

	std::cout << "(";
	if (t->getLeft()) {
		Node& left = *(t->getLeft());
		left.visit(*this);
	}

	std::cout << " " << t->getStringValue() << " ";

	if (t->getRight()) {
		Node& right = *(t->getRight());
		right.visit(*this);
	}

	std::cout << ")";
}

int main() {

	// build a tree
	TreeNode* tree = new TreeNode(new Leaf(2), new TreeNode(new Leaf(3), new Leaf(4), "*"), "+");
	
	// perform built-in operation on the tree
//	tree->op();
	NodeVisitor nv;
	nv.op(tree);
	std::cout << '\n';

	// destroy the tree
	delete tree;
}