#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

enum brace_type {ORIENTED_OPEN = '<', ORIENTED_CLOSE = '>', REGULAR_OPEN = '{', REGULAR_CLOSE = '}'}; // Типы скобок
enum mnogestvo_type {ORIENTED, REGULAR}; // Тип множества - ориентированное или нет
enum element_type {SINGLE, MNOGESTVO}; // Тип эл-та - множество или объект

class Mnogestvo;
class Element;
class Operators;

class Element
{
private:
element_type _type; // тип эл-та
public:
string value; // отдельное знач. эл-та
Mnogestvo * mn0gestvo; // знач эл-та множества
Element(element_type);
~Element();
const element_type type() const;
void setValue(string &);
void setValue(Mnogestvo *);
string toString() const;
bool operator<(const Element &) const;
};

class Mnogestvo
{
private:
vector<Element> elements; // вектор для эл-та множества
mnogestvo_type _type; // тип множества
Element * _getElementPtr(string &, unsigned int &, unsigned int);
bool _checkBalance(string &);
public:
bool isSorted;
bool isCorrect;
Mnogestvo(mnogestvo_type);
Mnogestvo(string &);
~Mnogestvo();
const mnogestvo_type type() const;
void pushElement(Element *);
void show(int);
int size();
void sort(bool);
string toString();
bool hasElement(string &);
friend class Operators;
};

class Operators
{
public:
bool isAsymmetric(Mnogestvo *);
};


Mnogestvo::Mnogestvo(mnogestvo_type tep)
{
// Конструктор
_type = tep; // tep - тип
isSorted = true;
}

Mnogestvo::Mnogestvo(string & strok)
{
// Конструктор
// strok - строка множества, определяемая автоматически
_type = REGULAR;
isSorted = true;
isCorrect = true;
if (!_checkBalance(strok))
{
cerr << "Nepravilnai stroka (proverte skobki): " << strok << endl;
isCorrect = false;
} else
{
unsigned int start = 1;
while (start < strok.length()-1)
{
Element * elt = _getElementPtr(strok, start, strok.length()-1);
if (elt != NULL)
pushElement(elt);
else
break;
}
if (strok != toString())
{
cerr << "Nepravilny vvod!" << endl;
cerr << " Polycheno: " << strok << endl;
cerr << " Preobrazyem, kak: " << toString() << endl;
isCorrect = false;
}
}
}

Mnogestvo::~Mnogestvo()
{
// TODO: fix memleaks
// vector<Element>::iterator i;
// for (i = elements.begin(); i < elements.end(); ++i)
// elements.erase(i);
}

const mnogestvo_type Mnogestvo::type() const
{
return _type; // тип возврощаемого множества
}

bool Mnogestvo::_checkBalance(string & str)
{
stack<char> braces;
for (unsigned int i = 1; i < str.length()-1; ++i)
{
if (str[i] == REGULAR_OPEN)
{
braces.push(REGULAR_OPEN);
} else if (str[i] == REGULAR_CLOSE)
{
if (braces.empty() || (!braces.empty() && braces.top() != REGULAR_OPEN))
return false;
else
braces.pop();
} else if (str[i] == ORIENTED_OPEN)
{
braces.push(ORIENTED_OPEN);
} else if (str[i] == ORIENTED_CLOSE)
{
if (braces.empty() || (!braces.empty() && braces.top() != ORIENTED_OPEN))
return false;
else
braces.pop();
}
}
return braces.empty();
}

Element * Mnogestvo::_getElementPtr(string & line, unsigned int & begin, unsigned int end)
{
// получения указателя
Mnogestvo * mnogestvo; // begin и end - выравнивание позиция для получения след. эл-та
if (line[begin] == REGULAR_OPEN)
{
mnogestvo = new Mnogestvo(REGULAR);
} else if (line[begin] == ORIENTED_OPEN)
{
mnogestvo = new Mnogestvo(ORIENTED);
}
Element * element = NULL;
if ((line[begin] >= '0' && line[begin] <= '9') || (line[begin] >= 'A' && line[begin] <= 'z'))
{
string child;
while (line[begin] != ',' && begin < end)
{
child = child+line[begin];
++begin;
}
++begin; // последний обрабатываемый эл-т
element = new Element(SINGLE);
element->setValue(child);
} else if (line[begin] == ORIENTED_OPEN)
{
unsigned int i = begin;
int braces = 0;
while (line[i] != ORIENTED_CLOSE || braces != 1)
{
if (line[i] == ORIENTED_OPEN)
++braces;
else if (line[i] == ORIENTED_CLOSE)
--braces;
++i;
}
element = new Element(MNOGESTVO);
Mnogestvo * mnogestvo;
mnogestvo = new Mnogestvo(ORIENTED);
++begin;
while (begin < i)
mnogestvo->pushElement(_getElementPtr(line, begin, i));
element->setValue(mnogestvo);
begin = i+2; // последний обрабатываемый эл-т
} else if (line[begin] == REGULAR_OPEN)
{
unsigned int i = begin;
int braces = 0;
while (line[i] != REGULAR_CLOSE || braces != 1)
{
if (line[i] == REGULAR_OPEN)
++braces;
else if (line[i] == REGULAR_CLOSE)
--braces;
++i;
}
element = new Element(MNOGESTVO);
Mnogestvo * mnogestv0;
mnogestv0 = new Mnogestvo(REGULAR);
++begin;
while (begin < i)
mnogestv0->pushElement(_getElementPtr(line, begin, i));
element->setValue(mnogestv0);
begin = i+2; // последний обрабатываемый эл-т
} else
{
begin = end;
}
return element;
}

void Mnogestvo::pushElement(Element * elementar)
{
// добовления нового эл-та во множество
elements.push_back(*elementar); //elementar - указатель на новый элемент
isSorted = false;
}

void Mnogestvo::show(int dsrt = 0)
{
vector<Element>::const_iterator i; // dsrt - глубина подмножества
for (i = elements.begin(); i != elements.end(); ++i)
{
for (int d = 0; d <= dsrt; ++d)
cout << " ";
if (i->type() == SINGLE)
{
cout << "Ob'ekt: " << i->value << endl;
} else
{
cout << "Mnogestvo (" <<
(i->mn0gestvo->type() == REGULAR ? "regular" : "oriented") <<
", " << (i->mn0gestvo->isSorted ? "sorted" : "unsorted") <<
"): " << endl;
i->mn0gestvo->show(dsrt+1);
}
}
}

int Mnogestvo::size()
{
return elements.size(); // размер возврощаемого множества
}

void Mnogestvo::sort(bool anyType = false)
{
// сортировка
if (isSorted && !anyType)
return;
if (type() == REGULAR || anyType)
{
std::sort(elements.begin(), elements.end());
} else
{
vector<Element>::iterator i; // рекурсивное сортировка
for (i = elements.begin(); i < elements.end(); ++i)
if (i->type() == MNOGESTVO)
i->mn0gestvo->sort();
}
if (!anyType)
isSorted = true;
}

string Mnogestvo::toString()
{
string mnogestvo = "";
vector<Element>::iterator i;
for (i = elements.begin(); i != elements.end(); ++i)
{
mnogestvo += i->toString();
if (i+1 != elements.end())
mnogestvo += ',';
}
if (type() == REGULAR)
mnogestvo = (char) REGULAR_OPEN + mnogestvo + (char) REGULAR_CLOSE;
else
mnogestvo = (char) ORIENTED_OPEN + mnogestvo + (char) ORIENTED_CLOSE;
return mnogestvo;
}

bool Mnogestvo::hasElement(string & el_t)
{
// проверка на присутстивие эл-та
vector<Element>::iterator i;
for (i = elements.begin(); i < elements.end(); ++i)
if (i->toString() == el_t)
return true;
return false;
}


Element::Element(element_type tip)
{
// конструктор элемента
_type = tip; // tip - тип элемента
value = "";
mn0gestvo = NULL;
}

Element::~Element()
{
// if (_type == MNOGESTVO)
// delete mnogestvo;;
}

void Element::setValue(string & val)
{
// Sets element value for single element
// val - string value
value = val;
}

void Element::setValue(Mnogestvo * sean)
{
// установление значение эл-та для множества
mn0gestvo = new Mnogestvo(sean->type()); // sean - указатель на целевое множество
*mn0gestvo = *sean;
}

const element_type Element::type() const
{
return _type; // тип возврощаемого эл-та
}

string Element::toString() const
{
if (type() == SINGLE)
return value;
else
return mn0gestvo->toString();
}

bool Element::operator<(const Element & qerl) const
{
// Оператор проверки неравенства элементов
if (type() == MNOGESTVO) // qerl - связь со значением переменной
mn0gestvo->sort();
if (qerl.type() == MNOGESTVO)
qerl.mn0gestvo->sort();
if (type() == SINGLE && qerl.type() == SINGLE)
return value < qerl.value;
else if (type() == MNOGESTVO && qerl.type() == MNOGESTVO)
return toString() < qerl.toString();
else if (type() == SINGLE && qerl.type() == MNOGESTVO)
return true;
else
return false;
}

bool Operators::isAsymmetric(Mnogestvo * mnogestvo)
{
mnogestvo->sort(true);
vector<string> elements;
vector<string>::iterator j;
vector<Element>::iterator i;
for (i = mnogestvo->elements.begin(); i < mnogestvo->elements.end(); ++i)
{
if (i->type() == MNOGESTVO)
{
i->mn0gestvo->sort(true);
bool alreadyHas = false;
for (j = elements.begin(); j < elements.end(); ++j)
{
if (i->toString() == (*j))
{
if (i->mn0gestvo->elements.size() > 1)
{
vector<Element>::iterator k;
for (k = i->mn0gestvo->elements.begin()+1; k < i->mn0gestvo->elements.end(); ++k)
{
if (k->toString() != i->mn0gestvo->elements.begin()->toString())
{
alreadyHas = true;
break;
}
}
} else
{
alreadyHas = true;
break;
}
}
}
if (alreadyHas)
return false;
else
elements.push_back(i->toString());
}
}
return true;
}

int main()
{
ifstream in("C:/relations.in"); //согласовать путь

string mnogestvoExpression;
getline(in, mnogestvoExpression);
in.close();

unsigned int pos = mnogestvoExpression.find("=");
if (pos != string::npos)
{
Operators * psycho = new Operators;
mnogestvoExpression = mnogestvoExpression.substr(pos+1);
Mnogestvo * mnogestvo = new Mnogestvo(mnogestvoExpression);

if (!mnogestvo->isCorrect)
{
cout << "Nepravilny vvod. EXIT" << endl;
} else
{
if (psycho->isAsymmetric(mnogestvo))
cout << "Assimetrichny" << endl;
else
cout << "Ne ssimetrichny" << endl;
}
} else
{
cout << "Nepravilny vvod. EXIT" << endl;
}

return 0;
}