#include <iostream>
#define EXPR_NUMBER_WEIGHT 3
#define EXPR_MUL_DIV_WEIGHT 2
#define EXPR_ADD_SUB_WEIGHT 1
#define EXPR_VARIABLE_WEIGHT 3
#define EXPR_BRACKET_WEIGHT 4
using namespace std;
typedef enum DataType {NIL = 0, INTEGER, FLOAT, VARIABLE, OPERATION};
///////////////////////////////////////////////////////////////////////////////
union DataVariant
{
int intData;
float floatData;
char * variable;
char operation;
long long longIntData;
};
///////////////////////////////////////////////////////////////////////////////
class UniData
{
public:
DataType type;
unsigned int weight;
union
{
int intData;
float floatData;
char * variable;
char operation;
long long longIntData;
};
public:
UniData()
{
type = NIL;
weight = 0;
memset(&intData, 0, sizeof(DataVariant));
}
UniData(DataType dt1, int dw1, int dd1)
{
type = dt1;
weight = dw1;
intData = dd1;
}
UniData(DataType dt1, int dw1, float dd1)
{
type = dt1;
weight = dw1;
floatData = dd1;
}
UniData(DataType dt1, int dw1, char od1)
{
type = dt1;
weight = dw1;
operation = od1;
}
UniData(DataType dt1, int dw1, char * dd1)
{
type = dt1;
weight = dw1;
variable = new char[strlen(dd1)+1];
strcpy(variable, dd1);
}
~UniData()
{
//if (variable && (type == VARIABLE))
// delete[] variable;
}
bool operator==(UniData & ud1)
{
if (type == ud1.type)
{
switch (type)
{
case INTEGER:
return intData == ud1.intData;
case FLOAT:
return floatData == ud1.floatData;
break;
case OPERATION:
return operation == ud1.operation;
break;
case VARIABLE:
return !strcmp(variable, ud1.variable);
break;
default:
return false;
break;
}
}
else
return false;
}
bool operator==(int id1)
{
return ((type == INTEGER) && (intData == id1));
}
bool operator==(float fd1)
{
return ((type == FLOAT) && (floatData == fd1));
}
char * GetAsStr(char * str)
{
switch(type)
{
case INTEGER:
sprintf(str, "%d", intData);
break;
case FLOAT:
sprintf(str, "%.3f", floatData);
break;
case OPERATION:
str[0] = operation;
break;
case VARIABLE:
strcpy(str, variable);
break;
default:
break;
}
return str;
}
};
///////////////////////////////////////////////////////////////////////////////
template <class Type>
class RingLink
{
////////////////////////////////////////////////////////////////////////////////
protected:
RingLink * next;
Type value;
int position;
////////////////////////////////////////////////////////////////////////////////
public:
RingLink()
{
next = this;
value = 0;
position = 0;
}
RingLink(int p1)
{
next = this;
position = p1;
}
RingLink(Type v1, int p1)
{
next = this;
value = v1;
position = p1;
}
////////////////////////////////////////////////////////////////////////////
Type & GetValue()
{
return value;
}
void SetValue(Type p1)
{
value = p1;
}
int GetPos()
{
return position;
}
void SetPos(int p1)
{
position = p1;
}
RingLink * GetNext()
{
return next;
}
RingLink * SetNext(RingLink * p1)
{
next = p1;
return p1;
}
RingLink * Add(RingLink * p1)
{
p1->next = next;
next = p1;
return p1;
}
void RemoveNext()
{
RingLink * rem = next;
next = next->next;
delete rem;
}
};
////////////////////////////////////////////////////////////////////////////////
template <class Type>
class VirtualArray
{
protected:
RingLink< Type > * ring;
int linkCount;
int maxLinkCount;
RingLink< Type > * CreateLink(int pos)
{
linkCount++;
return new RingLink< Type >(pos);
}
void RemoveNextLink(RingLink< Type > * link)
{
linkCount--;
link->RemoveNext();
}
public:
VirtualArray()
{
ring = NULL;
linkCount = 0;
maxLinkCount = 0;
}
int GetLenght()
{
return linkCount;
}
Type & operator[](int pos)
{
RingLink< Type > * curr = ring, * prev = NULL;
if (ring)
{
do
{
if (curr->GetPos() == pos)
return curr->GetValue();
prev = curr;
curr = curr->GetNext();
if (curr->GetValue() == 0)
{
if (curr != ring)
{
RemoveNextLink(prev);
curr = prev->GetNext();
}
else
{
RemoveNextLink(prev);
curr = prev->GetNext();
ring = curr;
}
}
}
while (curr != ring);
return ring->Add(CreateLink(pos))->GetValue();
}
else
{
ring = CreateLink(pos);
return ring->GetValue();
}
}
void Clear()
{
if (ring)
{
RingLink< Type > * curr = ring->GetNext(), * prev = NULL;
while (curr != ring)
{
prev = curr;
curr = (curr->GetNext());
delete prev;
}
linkCount = 0;
delete ring;
ring = NULL;
}
}
void Shift(int p1, int m1 = 0)
{
RingLink< Type > * curr = ring;
int sc = 0;
if (m1 && (m1 < linkCount))
m1 = linkCount;
do
{
if (m1 && ((curr->GetPos() + p1) >= m1))
curr->SetPos(sc++);
else
curr->SetPos(curr->GetPos() + p1);
curr = curr->GetNext();
}
while (curr != ring);
}
void Print()
{
RingLink< Type > * curr = NULL;
if (ring)
{
curr = ring->GetNext();
cout << "[" << ring->GetValue();
while (curr != ring)
{
cout << ", " << curr->GetValue();
curr = curr->GetNext();
}
cout << "]" << endl;
}
}
};
///////////////////////////////////////////////////////////////////////////////
template< class Type >
class Node
{
protected:
public:
Type data;
Node * up;
Node * left;
Node * right;
public:
Node()
{
up = NULL;
left = NULL;
right = NULL;
}
Node(Type d1)
{
data = d1;
up = NULL;
left = NULL;
right = NULL;
}
Node * Add(Node * nn)
{
// char str[16];
// memset(str, 0, 16);
// cout << " | " << nn->data.GetAsStr(str) << " | ";
if (nn->data.weight < data.weight)
{
if (up)
return up->Add(nn);
else
{
nn->Add(this);
return nn;
}
} else
if (nn->data.weight == data.weight)
{
if (up)
return up->Add(nn);
else
{
unsigned int oldWeight = nn->data.weight;
nn->data.weight = data.weight-1;
nn->Add(this);
nn->data.weight = oldWeight;
return nn;
}
} else
{
if (left)
{
if (right)
{
nn->Add(right);
nn->up = this;
return right = nn;
}
else
{
nn->up = this;
right = nn;
return right;
}
}
else
{
nn->up = this;
left = nn;
return left;
}
}
}
Node * Top()
{
if (up)
return up->Top();
else
return this;
}
Node * Delete()
{
if (left)
{
left->Delete();
delete left;
left = NULL;
}
if (right)
{
right->Delete();
delete right;
right = NULL;
}
if (up)
{
if (up->left == this)
up->left = NULL;
if (up->right == this)
up->right = NULL;
}
return this;
}
void Print(int lev = 0, unsigned int br0 = 0)
{
char str[16];
memset(str, 0, 16);
unsigned int br1 = (unsigned int) data.weight / EXPR_BRACKET_WEIGHT;
if (left && right)
for (unsigned int j=0; j<br1-br0; j++)
cout << "(";
if (left)
left->Print(lev+1, br1);
cout << data.GetAsStr(str);// lev << ": " << endl;
if (right)
right->Print(lev+1, br1);
if (left && right)
for (unsigned int j=0; j<br1-br0; j++)
cout << ")";
//br0 = br1;
}
bool operator==(Node & nn)
{
// char str[16];
// memset(str, 0, 16);
// cout << endl << data.GetAsStr(str);
// memset(str, 0, 16);
// if (left) cout << " | " << left->data.GetAsStr(str);
// memset(str, 0, 16);
// if (right) cout << " | " << right->data.GetAsStr(str);
bool rez = true;
rez = rez && (data==nn.data);
//// if (!rez) cout << 1 << endl;
rez = rez && ((left && nn.left) ? (* left)==(* nn.left) : left==nn.left);
// if (!rez) cout << 2 << endl;
rez = rez && ((right && nn.right) ? (* right)==(* nn.right) : right==nn.right);
// if (!rez) cout << 3 << endl;
return rez;
}
Node * Find(Node * sn)
{
if ((* this) == (* sn))
{
return this;
}
else
{
Node * fn = NULL;
if (left)
fn = left->Find(sn);
if (fn)
return (fn);
if (right)
fn = right->Find(sn);
if (fn)
return (fn);
}
return NULL;
}
void Conversion(Node * rn)
{
if ((data->type == OPERATION) && (data->operation == "*"))
{
if ((left->data->type == OPERATION) && (left->data->operation == "*"))
{
left->Conversion(rn);
}
if ((right->data->type == OPERATION) && (right->data->operation == "*"))
{
right->Conversion(rn);
}
}
else
{
Node * fn = rn->Find(this);
if (fn)
////!!!!!!!
}
}
void Rehash()
{
if ((data.type == OPERATION) && (data.operation == '-') && left && right)
{
if ((left->data.type == OPERATION) && (right->data.type == OPERATION) && (left->data.operation == '*') && (right->data.operation == '*'))
if (!((* left) == (* right)))
{
if (left) ;//
}
}
if (left)
left->Rehash();
if (right)
right->Rehash();
}
};
///////////////////////////////////////////////////////////////////////////////
typedef enum ParserState { PS_START, PS_NUMBER, PS_OPERATION, PS_STRING };
class Expression
{
protected:
VirtualArray< UniData > subjects;
unsigned int subjQty;
public:
Node< UniData > * tree;
public:
Expression()
{
subjQty = 0;
}
void AddNumber(char * nstr1, unsigned int nw1)
{
float rnum = .0;
sscanf(nstr1, "%f", &rnum);
UniData ud1(FLOAT, nw1 + EXPR_NUMBER_WEIGHT, rnum);
subjects[subjQty++] = ud1;
}
void AddOperation(char op1, unsigned int nw1)
{
unsigned int adw = 0;
if ((op1 == '+') || (op1 == '-'))
{
adw = EXPR_ADD_SUB_WEIGHT;
} else
if ((op1 == '*') || (op1 == '/'))
{
adw = EXPR_MUL_DIV_WEIGHT;
}
UniData ud1(OPERATION, nw1 + adw, op1);
subjects[subjQty++] = ud1;
}
void AddVariable(char * var1, unsigned int nw1)
{
UniData ud1(VARIABLE, nw1 + EXPR_VARIABLE_WEIGHT, var1);
subjects[subjQty++] = ud1;
}
void ParseStr(char * estr1)
{
unsigned int step = 0;
ParserState state = PS_START;
subjects.Clear();
subjQty = 0;
char buff[256] = "";
unsigned int subjlen = 0;
unsigned int weight = 0;
char cch = 0;
do
{
cch = estr1[step];
if (cch == ' ')
{
step++;
continue;
}
switch (state)
{
case PS_START:
if (((cch >= '0') && (cch <= '9')) || (cch == '.'))
{
state = PS_NUMBER;
} else
if ((cch == '+') || (cch == '-') || (cch == '*') || (cch == '/'))
{
state = PS_OPERATION;
} else
if (((cch >= 'A') && (cch <= 'Z')) || ((cch >= 'a') && (cch <= 'z')) || (cch == '_'))
{
state = PS_STRING;
} else
if (cch == '(')
{
weight += EXPR_BRACKET_WEIGHT;
step++;
} else
if (cch == ')')
{
weight -= EXPR_BRACKET_WEIGHT;
step++;
}
break;
case PS_NUMBER:
if (((cch >= '0') && (cch <= '9')) || (cch == '.'))
{
buff[subjlen++] = cch;
step++;
}
else
{
buff[subjlen] = 0;
subjlen = 0;
AddNumber(buff, weight);
state = PS_START;
}
break;
case PS_OPERATION:
AddOperation(cch, weight);
state = PS_START;
step++;
break;
case PS_STRING:
if (((cch >= 'A') && (cch <= 'Z')) || ((cch >= 'a') && (cch <= 'z')) || (cch == '_'))
{
buff[subjlen++] = cch;
step++;
}
else
{
buff[subjlen] = 0;
subjlen = 0;
AddVariable(buff, weight);
state = PS_START;
}
break;
}
}
while (cch);
}
void Print()
{
unsigned int br1 = 0, br0 = 0;
for (unsigned int i=0; i<subjQty; i++)
{
br1 = (unsigned int) subjects[i].weight / EXPR_BRACKET_WEIGHT;
for (unsigned int j=br0; j<br1; j++)
cout << "(";
for (unsigned int j=br1; j<br0; j++)
cout << ")";
br0 = br1;
switch (subjects[i].type)
{
case INTEGER:
cout << subjects[i].intData;
break;
case FLOAT:
cout << subjects[i].floatData;
break;
case OPERATION:
cout << subjects[i].operation;
break;
case VARIABLE:
cout << subjects[i].variable;
break;
}
}
}
void MakeTree()
{
tree = new Node< UniData >(subjects[0]);
for (unsigned int i=1; i<subjQty; i++)
{
char str[16];
memset(str, 0, 16);
tree = tree->Add(new Node< UniData >(subjects[i]));
}
tree = tree->Top();
}
void PrintTree()
{
tree->Print();
}
bool operator==(Expression & ex1)
{
return (* tree) == (* ex1.tree);
}
};
///////////////////////////////////////////////////////////////////////////////
int main()
{
char input[] = "a+b+c";
Expression expr1, expr2;
expr1.ParseStr(input);
expr1.MakeTree();
// expr2.ParseStr(input);
// expr2.MakeTree();
expr1.PrintTree();
UniData ud1(VARIABLE, 0, "g");
Node< UniData > nd(ud1);
if (expr1.tree->Find(&nd)) cout << "!!!!!!!!!";
cout << endl;
// if (expr1 == expr2) cout << endl << "!!!!!!!!!!!!!";
getchar();
return 0;
}