/*
Arden's Rule

    lambda:= {empty word}
    empty:= empty set
    0:= {'0'}
    1:= {'1'}

    a+b:= union of a and b
    a b:= concatenation of a and b
    a*:=  Kleene's closure of a.

    All regular expressions must end with  "."

We want to solve the system:

	E1= a11 E1 + a12 E1 + ... + a1n En + b1
	E2= a21 E1 + a22 E1 + ... + a2n En + b2
        ...
	En= an1 E1 + an2 E1 + ... + ann En + bn

assuming a_ij does not contain lambda.

Input:
     n
     a11.  a12.  ... a1n.  b1.
     a21.  a22.  ... a2n.  b2.
     ...
     an1.  an2.  ... ann.  bn.

Output:
     Solving values for E1,...,En 


Compile this program with g++ on any system
     g++ Arden.cpp -o Arden
Execute:
     ./Arden

				Eduardo Viruena Silva
				November, 2003
*/



#include <iostream>
#include <cstdlib>
#include <cctype>
#include <cstring>

#define debug(x)  { cerr << "debug:" << (x) << endl; }
//------------------------------------------------//
// Objects for handling regular expression trees  //
//------------------------------------------------//

using namespace std;

enum { LETTER, EMPTY, LAMBDA, UNION, CONCAT, CLOSURE };

class Node {
       public:
         virtual ~Node() 
                   {};
         virtual int type(void) = 0;
         virtual Node* copy(void) = 0;
         virtual Node* simp(void) = 0;
         virtual ostream& print(ostream& os) = 0;
      };

class Letter: public Node  {
       private:
         char ch;
       public:
         Letter(char c)
                   { ch= c; };
         virtual ~Letter(void) 
                   { };
         virtual int type(void)
                   { return LETTER; };
         virtual Node* copy(void)
                   { return new Letter(ch); };
         virtual Node* simp(void)
                   { return copy(); };
         virtual ostream& print(ostream& os);
      };


ostream& Letter::print(ostream& os)
  {
   os << ch;
  }


class Empty: public Node {
       public:
         virtual ~Empty(void) 
                   { };
         virtual int type(void)
                   { return EMPTY; };
         virtual Node* copy(void)
                   { return new Empty(); };
         virtual Node* simp(void)
                   { return copy(); };
         virtual ostream& print(ostream& os);
      };

ostream& Empty::print(ostream& os)
  {
   return  os << "empty";
  }

class Lambda: public Node {
       public:
         Lambda(void) {};
         virtual ~Lambda(void) 
                   { };
         virtual int type(void)
                   { return LAMBDA; };
         virtual Node* copy(void)
                   { return new Lambda(); };
         virtual Node* simp(void)
                   { return copy(); };
         virtual ostream& print(ostream& os);
      };

ostream& Lambda::print(ostream& os)
  {
   os << "lambda";
  }


class BinOp : public Node {
       protected:
         Node* left;
         Node* right;
       public:
         BinOp(Node* l, Node* r)
                 {  left= l;   right= r;  };
         virtual ~BinOp(void)
                 {
                  delete right;
                  delete left;
                 }
         virtual int type(void) = 0;
         virtual Node* copy(void) = 0;
         virtual Node* simp(void) = 0;
         virtual ostream& print(ostream& os) = 0;
};


class Union: public BinOp {
       public:
         Union(Node* l, Node* r) : BinOp(l,r) {};
         virtual ~Union(void) 
                   { };
         virtual int type(void)
                   { return UNION; };
         virtual Node* copy(void)
                   { return new Union(left->copy(), right->copy()); };
         virtual Node* simp(void);
         virtual ostream& print(ostream& os);
      };


ostream& Union::print(ostream& os)
  {
   left->print(os);
   os << " + ";
   right->print(os);
  }

Node* Union::simp(void)
{
   Node* l= left->simp();
   Node* r= right->simp();

   int tl= l->type();
   int tr= r->type();

   if (tl==EMPTY)
      {
       delete l;
       return r;
      }
   if (tr==EMPTY)
      {
       delete r;
       return l;
      }

   if (tl==CLOSURE && tr==LAMBDA)
      {
       delete r;
       return l;
      }
   if (tr==CLOSURE && tl==LAMBDA)
      {
       delete l;
       return r;
      }

   return new Union(l,r);
}


class Concatenation: public BinOp {
       public:
         Concatenation(Node* l, Node* r) : BinOp(l, r)
                   { };
         ~Concatenation(void)
                   { };
         virtual int type(void)
                   { return CONCAT; };
         virtual Node* copy(void)
                   { return new Concatenation(left->copy(), right->copy()); };
         virtual Node* simp(void);
         virtual ostream&  print(ostream& os);
      };

ostream&  Concatenation::print(ostream& os)
  {
   if (left->type() == UNION)
       os << '(';
   left->print(os);
   if (left->type() == UNION)
       os << ')';

   if (left->type() == UNION)
       os << '(';
   right->print(os);
   if (left->type() == UNION)
       os << ')';
  }

Node* Concatenation::simp(void)
{
   Node* l= left->simp();
   Node* r= right->simp();

   int  tl= l->type(); 
   int  tr= r->type(); 

   if (tl==EMPTY)
      {
       delete r;
       return l;
      }

   if (tr==EMPTY)
      {
       delete l;
       return r;
      }

   if (tl==LAMBDA)
      {
       delete l;
       return r;
      }

   if (tr==LAMBDA)
      {
       delete r;
       return l;
      }

   return new Concatenation(l,r);
}


class Closure: public Node {
       private:
         Node* left;
       public:
         Closure(Node* l)
                   { left= l; };
         ~Closure(void)
                   { delete left; };
         virtual int type(void)
                   { return CLOSURE; };
         virtual Node* copy(void)
                   { return new Closure(left->copy()); };
         virtual Node* simp(void);
         virtual ostream& print(ostream& os);
      };

ostream& Closure::print(ostream& os)
  {
   int t= left->type();
   if (t==UNION || t==CONCAT)
      os << '(';
   left->print(os);
   if (t==UNION || t==CONCAT)
      os << ')';
   os << "*";
  }

Node* Closure::simp(void)
{
   Node* l= left->simp();
   int  tl= l->type();

   if (tl==EMPTY)
      {
       delete l;
       return new Lambda();
      }

   if (tl==LAMBDA)
      {
       delete l;
       return new Lambda();
      }

   if (tl==CLOSURE)
      return l;

   return new Closure(l);
}


//---------------------------//
// Regular Expression parser //
//---------------------------//

class Parser {
       private:
         int  ch;
         char sym[20];
         int  ks;

         void initsym(void)  { ks= 0; }
         void getch(void)    { ch= cin.get(); if (ch==EOF) ch='.'; };
         void putch(char c)  { sym[ks++]= c; };
         void endsym(void)   { sym[ks]= '\0'; }

         void error(const char* msg);
         int test(const char* str);
         int testg(const char* str, const char* mesg=NULL);

         void GetSym(void);

         Node* Primary(void);
         Node* Factor(void);
         Node* Term(void);
         Node* Expr(void);

       public:
         Parser(void);
         Node* ExpReg(void);
      };

void Parser::error(const char* msg)
  {
   cerr << "Error: " << msg << endl;
   exit(1);
  }

int Parser::test(const char* str)
  {
   return strcmp(sym,str) ? 0 : 1;
  }

int Parser::testg(const char* str, const char* mesg)
  {
   if(test(str))
     {
      GetSym();
      return 1;
     }
   if (mesg)
      error(mesg);
   return 0;
  }

Parser::Parser(void)
  {
   ch= ' ';
   strcpy(sym,"");
  }

void Parser::GetSym(void)
  {
   while (isspace(ch))
     getch();
   initsym();
   while (isalpha(ch))
     {
      putch(ch);
      getch();
     }
   if (ks)
     {
      endsym();
      return;
     }
   switch (ch)
     {
      case '.' :
      case ')' :
      case '(' :
      case '*' :
      case '+' :
      case '1' :
      case '0' :  putch(ch);
      default  :  getch();
                  endsym();
                  return;
     }
  }

Node* Parser::Primary(void)
  {
   if (testg("empty"))
     return Create("empty", NULL, NULL);

   if (testg("lambda"))
     return Create("lambda", NULL, NULL);

   if (testg("0"))
     return Create("0", NULL, NULL);

   if (testg("1"))
     return Create("1", NULL, NULL);

   if (testg("(", "Missing <primary>"))
     {
      Node* p= Expr();
      if (testg(")", "Missing ')'"))
         return p;
     }
  }

Node* Parser::Factor(void)
  {
   Node* f= Primary();
   while (testg("*"))
      f= Create("*", f, NULL);
   return f;
  }

Node* Parser::Term(void)
  {
   Node* t= Factor();
   while(test("lambda") || test("empty") || test("0") || test("1") || test("("))
      t= Create("", t, Factor());
   return t;
  }

Node* Parser::Expr(void)
  {
   Node* e= Term();
   while(testg("+"))
      e= Create("+", e, Term());
   return e;
  }

Node* Parser::ExpReg(void)
  {
   Node* e;
   ch= ' ';
   GetSym();
   e= Expr();
   if (test("."))
      return e;

   error("Missing '.'");
  }




int main(void)
{
   Node* u= new Union(new Closure(new Letter('0')), new Empty());

   u->print(cout);
   cout << endl;

   Node* s= u->simp();
   s->print(cout);
   cout << endl;
   delete u;
}