Algebraic substitution trees, expand variables to subtree with cloning

miniCas.cpp

#include <memory>
#include <string>
#include <vector>
#include <assert.h>

using namespace std;

enum Type { tEmpty, tNum, tVar, tFrac, tProd, tSum };
enum Precedence { precStart, precSum, precFrac, precAtom };

class Node
{
protected:
	vector<shared_ptr<Node>> childs;
	int level = 0;
public:
	Type type = tEmpty;
	Node* parent = nullptr;//not shared_ptr! because of memory leaks of circular dependency
	Node()
	{
	}
	~Node()
	{
	}

	shared_ptr<Node> cloneTree()
	{
		shared_ptr<Node> newElem = cloneOne();
		for (size_t i = 0; i<childs.size(); i++)
		{
			shared_ptr<Node> subElem = childs[i]->cloneTree();
			newElem->AddOneChild(subElem);
		}
		newElem->setLevel(0);
		return newElem;
	}

	virtual string s() = 0;

	string sprec(string str)
	{
		if (sign || parent != nullptr && precedence() <= parent->precedence())
			str = "(" + str + ")";
		if (sign) str = "-" + str;
		return str;
	}

	virtual shared_ptr<Node> cloneOne() = 0;

	bool sign = false;

	void setSign()
	{
		sign = true;
	}

	Precedence precedence()
	{
		switch (type)
		{
		case tNum: return precAtom;
		case tVar: return precAtom;
		case tFrac: return precFrac;
		case tSum: return precSum;
		default: return precStart;
		}
	}

	string typeStr()
	{
		switch (type)
		{
		case tNum: return "Num";
		case tVar: return "Var";
		case tFrac: return "Frac";
		case tSum: return "Sum";
		default: return "Start";
		}
	}

	void erase()
	{
		childs.clear();
	}
	void deleteChild(int index)
	{
		childs.erase(childs.begin()+index);
	}

	void setLevel(int level)
	{
		this->level = level;
		for (size_t i = 0; i<childs.size(); i++)
			childs[i]->setLevel(level+1);
	}

	void AddOneChild(shared_ptr<Node> node)
	{
		childs.push_back(node);
		node->parent = this;
	}

	void InsertOneChild(int index, shared_ptr<Node> node)
	{
		childs.insert(childs.begin() + index, node);
		node->parent = this;
	}

	void AddTree(shared_ptr<Node> subtree)
	{
		shared_ptr<Node> clone = subtree->cloneTree();
		AddOneChild(clone);
		clone->setLevel(level+1);
	}

	void InsertTree(int index, shared_ptr<Node> subtree)
	{
		shared_ptr<Node> clone = subtree->cloneTree();
		InsertOneChild(index, clone);
		clone->setLevel(level + 1);
	}

	void ReplaceChild(int index, shared_ptr<Node> subtree, bool bClone = true)
	{
		if (bClone)
			subtree = subtree->cloneTree();
		deleteChild(index);
		InsertOneChild(index, subtree);
		subtree->setLevel(level + 1);
	}

	void ReplaceChild(Node* child, shared_ptr<Node> subtree, bool bClone = true)
	{
		int index = -1;
		for (int i=0; i<childs.size(); i++)
			if (childs[i].get()==child)
			{
				index = i;
				break;
			}
		if (index<0) throw "not found child for replace";
		ReplaceChild(index, subtree, bClone);
	}

	shared_ptr<Node>& at(int index)
	{
		return childs[index];
	}

	virtual void findVar(string varName, vector<Node*> &findVec)
	{
		if (type==tVar)
		{
			findVar(varName, findVec);
		}
		else for (size_t i = 0; i<childs.size(); i++)
			childs[i]->findVar(varName, findVec);
	}

	void print()
	{
		for (int i = 0; i<level; i++)
			printf("  ");
		printf("(%d) ", precedence());
		printf("%s",s().c_str());
		//if (parent) printf("->%s", parent->s().c_str());
		printf("\n");
		for (size_t i=0; i<childs.size(); i++)
			childs[i]->print();
	}
};

class Num : public Node
{
	uint64_t nom, den;
	shared_ptr<Node> cloneOne()
	{
		shared_ptr<Node> result = make_shared<Num>(nom);
		return result;
	}
public:
	Num(uint64_t number) :Node()
	{
		nom = number;
		den = 1;
		type = tNum;
	}
	string s()
		//dla postaci liczbnik i mianownik potrzebne nawiasy dla dzielenia i znaku 1/2/x, x/1/2
		//zwrca pred = atom lub frac a jak uniknąć -(1/2) czy -1/2 ?
	{
		assert(childs.size() == 0);
		return to_string(nom);
		/*
		string res = to_string(nom);
		if (den!=1)
		res += "/"+ to_string(den);
		return res;

		*/
	}

};

class Var : public Node
{
	string name;
	shared_ptr<Node> cloneOne()
	{
		shared_ptr<Node> result = make_shared<Var>(name);
		return result;
	}
public:
	Var(string name) :Node()
	{
		this->name = name;
		type = tVar;
	}

	string s()
	{
		assert(childs.size() == 0);
		return name;
	}

	void findVar(string varName, vector<Node*> &findVec)
	{
		if (name==varName)
			findVec.push_back(this);
	}
};

class Frac : public Node
{
	/*	shared_ptr<Node> clone()
	{
	shared_ptr<Frac> result = make_shared<Frac>();
	copyMembers(result);
	return static_pointer_cast<Node>(result);
	}*/
	shared_ptr<Node> cloneOne()
	{
		shared_ptr<Node> result = make_shared<Frac>();
		return result;
	}
public:
	Frac()
	{
		type = tFrac;
	}

	Frac(shared_ptr<Node> nom, shared_ptr<Node> den):Frac()
	{
		AddTree(nom);
		AddTree(den);
	}

	string s()
	{
		string res;
		if (childs.size() == 2)
		{
			res = childs[0]->s();
			res += "/" + childs[1]->s();
		}
		else res = "error_frac";
		return sprec(res);
	}
};

class Sum : public Node
{
	shared_ptr<Node> cloneOne()
	{
		shared_ptr<Node> result = make_shared<Sum>();
		return result;
	}
public:
	Sum()
	{
		type = tSum;
	}

	Sum(vector<shared_ptr<Node>> &sumvec): Sum()
	{
		for (size_t i = 0; i<sumvec.size(); i++)
			AddTree(sumvec[i]);
	}

	string s()
	{
		//if (childs.size()<=1) return "error_sum";
		//assert(childs.size()>1);
		string res = "";
		for (size_t i = 0; i<childs.size(); i++)
		{
			if (i>0 && !childs[i]->sign)
				res += "+";
			res += childs[i]->s();
		}
		return sprec(res);
	}
};


class Formula
{
public:
	shared_ptr<Node> root;
	Formula& operator=(const Formula &f)
	{ 
		root = f.root;
	}

	void substVar(string varName, shared_ptr<Node> expr, Formula &out)
	{
		out.root = root->cloneTree();
		vector<Node*> findVec;
		out.root->findVar(varName, findVec);
		shared_ptr<Node> clone = nullptr;
		for (int i = 0; i<findVec.size(); i++)
		{
			Node* parent = findVec[i]->parent;
			if (parent)
			{
				if (clone)
					clone = clone->cloneTree();
				else
					clone = expr->cloneTree();
				parent->ReplaceChild(findVec[i], clone, false);
			}
		}
	}

	void print()
	{
		if (root) root->print();
	}
};

int main()
{
	Formula f,f1;
	shared_ptr<Node> x0 = make_shared<Var>("x");
	shared_ptr<Node> n0 = make_shared<Var>("n");
	shared_ptr<Node> n_x0 = make_shared<Frac>(n0, x0);
	//n_x0->print();

	vector<shared_ptr<Node>> sumvec = { x0, n_x0 };	

	shared_ptr<Node> sum0 = make_shared<Sum>(sumvec);

	shared_ptr<Node> num2 = make_shared<Num>(2);
	f.root = make_shared<Frac>(sum0, num2);
	
	f.print();
	f1.print();
	f.substVar("x", f.root, f1);
	f.print();
	f1.print();
	f1.substVar("x", f.root, f1);
	f.print();
	f1.print();
	return 0;
}