#include <iostream>
using namespace std;

class Regex
{
public:
	virtual void Print(ostream& ostr) const = 0;
	virtual Regex* Clone() const = 0;

	virtual Regex* basic() const
	{
		return Clone();
	}

	virtual ~Regex()
	{}
};

class RegexChar : public Regex
{
public:
	RegexChar(char ch)
		: _ch(ch)
	{	
	}

	virtual void Print(ostream& ostr) const
	{
		ostr<<_ch;
	}

	virtual Regex* Clone() const
	{
		return new RegexChar(*this);
	}


private:
	char _ch;
};


class RegexEPS : public Regex
{
public: 
	virtual void Print(ostream& ostr) const
	{	ostr<<"eps";	}


	virtual Regex* Clone() const 
	{    return new RegexEPS(); }
};

class RegexCharClass : public Regex
{
public:
	RegexCharClass(char from, char to)
		: _from(from), _to(to)
	{	
	}

	virtual void Print(ostream& ostr) const
	{
		ostr<<"["<<_from<<"-"<<_to<<"]";
	}

	virtual Regex* Clone() const
	{
		return new RegexCharClass(*this);
	}


private:
	char _from, _to;
};

class RegexUnaryOp : public Regex
{
public:
	RegexUnaryOp(Regex *r1)
		:_r1(r1)
	{}

	RegexUnaryOp(const RegexUnaryOp& r)
		:  _r1(r._r1->Clone())
	{}

	virtual ~RegexUnaryOp()
	{	delete _r1;	}

protected:
	Regex *_r1;
};

class RegexBinaryOp : public Regex
{
public:
	RegexBinaryOp(Regex *r1, Regex *r2)
		:_r1(r1), _r2(r2)
	{}

	RegexBinaryOp(const RegexBinaryOp& r)
		:  _r1(r._r1->Clone()), _r2(r._r2->Clone())
	{}

	virtual ~RegexBinaryOp()
	{	delete _r1;
		delete _r2;
	}

protected:
	Regex *_r1, *_r2;
};

class RegexConcat : public RegexBinaryOp
{ 
public:

	RegexConcat(Regex *r1, Regex *r2)
		: RegexBinaryOp(r1, r2)
	{}

	virtual void Print(ostream& ostr) const
	{
		cout<<"(";
		_r1->Print(ostr);
		cout<<")(";
		_r2->Print(ostr);
		cout<<")";
	}

	virtual Regex* Clone() const
	{
		return new RegexConcat(*this);
	}

	virtual Regex* basic() const
	{
		return new RegexConcat(_r1->basic(), _r2->basic());
	}
};

class RegexDisj : public RegexBinaryOp
{ 
public:

	RegexDisj(Regex *r1, Regex *r2)
		: RegexBinaryOp(r1, r2)
	{}

	virtual void Print(ostream& ostr) const
	{
		ostr<<"(";
		_r1->Print(ostr);
		ostr<<")|(";
		_r2->Print(ostr);
		ostr<<")";
	}

	virtual Regex* Clone() const
	{
		return new RegexDisj(*this);
	}

	virtual Regex* basic() const
	{
		return new RegexDisj(_r1->basic(), _r2->basic());
	}
};

class RegexTIMES : public RegexUnaryOp
{ 
public:

	RegexTIMES(Regex *r1)
		: RegexUnaryOp(r1)
	{}


	virtual void Print(ostream& ostr) const
	{
		ostr<<"(";
		_r1->Print(ostr);
		ostr<<")*";
	}

	virtual Regex* Clone() const
	{
		return new RegexTIMES(*this);
	}

	virtual Regex* basic() const
	{
		return new RegexTIMES(_r1->basic());
	}
};


class RegexQM : public RegexUnaryOp
{ 
public:

	RegexQM(Regex *r1)
		: RegexUnaryOp(r1)
	{}

	virtual void Print(ostream& ostr) const
	{
		ostr<<"(";
		_r1->Print(ostr);
		ostr<<")?";
	}

	virtual Regex* Clone() const
	{
		return new RegexQM(*this);
	}

	virtual Regex* basic() const
	{
		return new RegexDisj(_r1->Clone(), new RegexEPS());
	}

};

class RegexPLUS : public RegexUnaryOp
{ 
public:

	RegexPLUS(Regex *r1)
		: RegexUnaryOp(r1)
	{}


	virtual void Print(ostream& ostr) const
	{
		ostr<<"(";
		_r1->Print(ostr);
		ostr<<")+";
	}

	virtual Regex* Clone() const
	{
		return new RegexPLUS(*this);
	}

	virtual Regex* basic() const
	{
		return new RegexConcat(_r1->Clone(), 
				     new RegexTIMES(_r1->Clone()));
	}
};


