%{

/* Januar2004. Resenje prakticnog dela ispita. 
   Autor : Filip Maric
*/

#include <stdlib.h>
#include <string.h>

/* Datoteka koja sadrzi definiciju svih 
   dopustenih tipova vrednosti izraza */
#include "types.h"

/* Funkcija obrade gresaka */
#define yyerror printf


/* Jedan cvor pretrazivackog drveta koje ce da sadrzi
   sve deklarisane promenjive i njihove vrednosti */
typedef struct _node
{    /* Tip promenjive */
     expression_type type;
     /* Ime promenjive */
     char* name;
     /* Vrednost promenjive */
     EXPRESSION_VALUE* value;

     /* Pokazivaci na potomke u drvetu */
     struct _node *left, *right;
} NODE;


/* Pomocna promenjiva koja sadrzi informaciju 
   o tipu promenjivih koje se upravo deklarisu */
expression_type current_type;

/* Pokazivac na koren drveta koje sadrzi sve promenjive */
NODE* tree=NULL;

%}

/*  YACC-ov interni stek vrednosti 
    moze da sadrzi podatke sledecih tipova :
*/

%union
{  /* Vrednosti dopustenih izraza */
   EXPRESSION_VALUE* expression_value;  
 
   /* Realne brojne vrednosti */
   float float_value;

   /* Tekstualne vrednosti */
   char* string_value;
};

/*Deklaracije tokena : 
    REAL_TYPE     odgovara rezervisanoj reci REAL
    COMPLEX_TYPE  odgovara rezervisanoj reci COMPLEX
    REAL_PART     odgovara rezerviseanoj reci real
    IMAG_PART     odgovara rezervisanoj reci imag
*/
%token  REAL_TYPE COMPLEX_TYPE REAL_PART IMAG_PART

/*    REAL_CONSTANT  odgovara realnoj konstanti (npr 2.343)
      IMAG_CONSTANT odgovara imaginarnoj konstanti (npr. 243.23i)

   Ovim tokenima odgovaraju realne brojne vrednosti na steku vrednosti.
   Postavljanje ovih vrednosti se vrsi u lex-delu programa */
%token <float_value>  REAL_CONSTANT IMAG_CONSTANT

/* Ovom tokenu odgovara tekstualna vrednost koja predstavlja ime promenjive.
   Vrednost se postavlja u lex-u */
%token <string_value> VARIABLE 

/* Ovim se postavlja prioritet i asocijativnost aritmetickih operatora i time
   se uklanja viseznacnost gramatike koja sledi */
%left '+' '-'
%left '*' '/'

/* Neterminalu expression na steku vrednosti odgovaraju vrednosti tipa EXPRESSION_VALUE* */
%type <expression_value> expression


%%
/* Gramatika */

/* Datoteka se sastoji od niza linija */
lines : lines line
      | line
      ;

/* Svaka linija je ili deklaracija promenjivih ili dodela vrednosti promenjivih */
line  :  type variables ';'
      |  VARIABLE '=' expression ';' 
         {  /*Pronalazimo promenjivu i postavljamo joj vrednost na vrednost izraza */
            FindVariableAndSetItsValue(tree,$1,$3); free($3); free($1); }
      ;

/* Niz promenjivih */
variables : variables ',' variable
          | variable
          ;

/* Promenjiva moze biti inicijalizovana i neinicijalizovana */
variable  :  VARIABLE '=' expression  
             {  /* Dodajemo promenjivu u drvo i postavljamo joj vrednost na vrednost izraza */
                AddVariable(&tree,$1,current_type,$3); }
          |  VARIABLE  
             { /*  Dodajemo promenjivu u drvo ali joj vrednost ne inicijalizujemo */
               AddVariable(&tree,$1,current_type,NULL); }
          ;

/* Dopusteni tipovi podataka. 
  U ovom trenutku pamtimo vrednost tekuceg tipa u current_type.  */
type  : REAL_TYPE    { current_type=REAL;    }
      | COMPLEX_TYPE { current_type=COMPLEX; }
      ;

/* Gramatika izraza */
expression :  /* Zbir dva izraza */
              expression '+' expression {$$=Add($1,$3); free($1); free($3); }
           |  /* Razlika dva izraza */
              expression '-' expression {$$=Subtract($1,$3); free($1); free($3); }
           |  /* Proizvod dva izraza */
              expression '*' expression {$$=Multiply($1,$3); free($1); free($3); }
           |  /* Kolicnik dva izraza */
              expression '/' expression {$$=Devide($1,$3); free($1); free($3); }
           |  '(' expression ')' { $$=$2; }
              /* Funkcija real koja odredjuje realni deo izraza */
           |  REAL_PART '(' expression ')' { $$=real_part($3); free($3); }
              /* Funkcija imag koja odredjuje imaginarni deo izraza */
           |  IMAG_PART '(' expression ')' { $$=imag_part($3); free($3); }                             
              /* Realna konstanta */
           |  REAL_CONSTANT {  $$=(EXPRESSION_VALUE*)malloc(sizeof(EXPRESSION_VALUE)); 
                               $$->type=REAL;
                               $$->real_value.real=$1;
                            }                             
              /* Imaginarna konstanta */
           |  IMAG_CONSTANT {     $$=(EXPRESSION_VALUE*)malloc(sizeof(EXPRESSION_VALUE)); 
                                  $$->type=COMPLEX;
                                  $$->complex_value.real=0.0;
                                  $$->complex_value.imag=$1;
                               }
           | VARIABLE { /* Na stek stavljamo kopiju vrednosti promenjive iz drveta */
                        EXPRESSION_VALUE* var_value = FindVariableValue(tree,$1);
                        $$=(EXPRESSION_VALUE*)malloc(sizeof(EXPRESSION_VALUE));

                        if (var_value==NULL)
			{  /* Ukoliko promenjiva nije definisana postavljamo vrednost 
                              ovog izraza na podrazumevanu */
                           $$->type=REAL;
			   $$->real_value.real=0.0;
                        }
                        else
                             memcpy($$,var_value,sizeof(EXPRESSION_VALUE)); 
                      } 
           ;

%%


	   /* FUNKCIJE ZA RAD SA IZRAZIMA */

/* Funkcija stampa vrednost izraza u citljivom obliku */
void Print(EXPRESSION_VALUE* e)
{    switch(e->type)
     {   case REAL:
             printf("%f",e->real_value.real);
             break;
         case COMPLEX:
             printf("%f+%fi",e->complex_value.real,e->complex_value.imag);
             break;
     }
}



/* Funkcija sabira dva broja i pri tom prilagodjava tip rezultata */
EXPRESSION_VALUE* Add(EXPRESSION_VALUE* e1, EXPRESSION_VALUE* e2)
{  /* Rezultat */
   EXPRESSION_VALUE* ev=(EXPRESSION_VALUE*)malloc(sizeof(EXPRESSION_VALUE));
   
   switch (e1->type)
   {	case COMPLEX:
	   switch (e2->type)
	   {	case COMPLEX:
	              /* Zbir dve kompleksne vrednosti */ 
                      ev->type=COMPLEX;
                      ev->complex_value.real=e1->complex_value.real+e2->complex_value.real;
                      ev->complex_value.imag=e1->complex_value.imag+e2->complex_value.imag;
	              break;
        	case REAL:
		      /* Zbir kompleksne i realne vrednosti */
                      ev->type=COMPLEX;
                      ev->complex_value.real=e1->complex_value.real+e2->real_value.real;
                      ev->complex_value.imag=e1->complex_value.imag;
	              break; 
	   }
           break;
        case REAL:
	   switch (e2->type)
	   {	case COMPLEX:
		      /* Zbir realne i kompleksne vrednosti */
                      ev->type=COMPLEX;
                      ev->complex_value.real=e1->real_value.real+e2->complex_value.real;
                      ev->complex_value.imag=e2->complex_value.imag;
	              break;
        	case REAL:
		      /* Zbir dve realne vrednosti */
                      ev->type=REAL;
                      ev->real_value.real=e1->real_value.real+e2->real_value.real;
	              break;
	   }
           break;
   }
   return ev;
}


/* Funkcija oduzima dva broja i pri tom prilagodjava tip rezultata */
EXPRESSION_VALUE* Subtract(EXPRESSION_VALUE* e1, EXPRESSION_VALUE* e2)
{  EXPRESSION_VALUE* ev=(EXPRESSION_VALUE*)malloc(sizeof(EXPRESSION_VALUE));
   
   switch (e1->type)
   {	case COMPLEX:
	   switch (e2->type)
	   {	case COMPLEX:
                      ev->type=COMPLEX;
                      ev->complex_value.real=e1->complex_value.real-e2->complex_value.real;
                      ev->complex_value.imag=e1->complex_value.imag-e2->complex_value.imag;
	              break;
        	case REAL:
                      ev->type=COMPLEX;
                      ev->complex_value.real=e1->complex_value.real-e2->real_value.real;
                      ev->complex_value.imag=e1->complex_value.imag;
	              break;
	   }
           break;
        case REAL:
	   switch (e2->type)
	   {	case COMPLEX:
                      ev->type=COMPLEX;
                      ev->complex_value.real=e1->real_value.real-e2->complex_value.real;
                      ev->complex_value.imag=-e2->complex_value.imag;
	              break;
        	case REAL:
                      ev->type=REAL;
                      ev->real_value.real=e1->real_value.real-e2->real_value.real;
	              break;
	   }
           break;
   }
   return ev;
}

/* Funkcija mnozi dva broja i pri tom prilagodjava tip rezultata */
EXPRESSION_VALUE* Multiply(EXPRESSION_VALUE* e1, EXPRESSION_VALUE* e2)
{  EXPRESSION_VALUE* ev=(EXPRESSION_VALUE*)malloc(sizeof(EXPRESSION_VALUE));
  
   switch (e1->type)
   {	case COMPLEX:
	   switch (e2->type)
	   {	case COMPLEX:
                      ev->type=COMPLEX;
                      ev->complex_value.real=e1->complex_value.real*e2->complex_value.real-
                                   e1->complex_value.imag*e2->complex_value.imag;
                      ev->complex_value.imag=e1->complex_value.real*e2->complex_value.imag+
                                   e1->complex_value.imag*e2->complex_value.real;
	              break;
        	case REAL:
                      ev->type=COMPLEX;
                      ev->complex_value.real=e1->complex_value.real*e2->real_value.real;
                      ev->complex_value.imag=e1->complex_value.imag*e2->real_value.real;
	              break;
	   }
           break;
        case REAL:
	   switch (e2->type)
	   {	case COMPLEX:
                      ev->type=COMPLEX;
                      ev->complex_value.real=e1->real_value.real*e2->complex_value.real;
                      ev->complex_value.imag=e1->real_value.real*e2->complex_value.imag;
	              break;
        	case REAL:
                      ev->type=REAL;
                      ev->real_value.real=e1->real_value.real*e2->real_value.real;
	              break;
	   }
           break;
   }

   return ev;
}


/* Funkcija deli dva broja i pri tom prilagodjava tip rezultata */
EXPRESSION_VALUE* Devide(EXPRESSION_VALUE* e1, EXPRESSION_VALUE* e2)
{  EXPRESSION_VALUE* ev=(EXPRESSION_VALUE*)malloc(sizeof(EXPRESSION_VALUE));
  
   switch (e1->type)
   {	case COMPLEX:
	   switch (e2->type)
	   {	case COMPLEX:
                 {     float denominator= e2->complex_value.real*e2->complex_value.real+
                                          e2->complex_value.imag*e2->complex_value.imag;

                      if (denominator==0.0)
                         yyerror("Division by zero");

                      ev->type=COMPLEX;
                      ev->complex_value.real=(e1->complex_value.real*e2->complex_value.real+
                                             e1->complex_value.imag*e2->complex_value.imag)/denominator;
                      ev->complex_value.imag=(e1->complex_value.imag*e2->complex_value.real-
                                             e1->complex_value.real*e2->complex_value.imag)/denominator;
	              break;
		}
        	case REAL:
		      if (e2->real_value.real==0)
     		          yyerror("Division by zero");

                      ev->type=COMPLEX;
                      ev->complex_value.real=e1->complex_value.real*e2->real_value.real;
                      ev->complex_value.imag=e1->complex_value.imag*e2->real_value.real;
	              break;
	   }
           break;
        case REAL:
	   switch (e2->type)
	   {	case COMPLEX:
                {     float denominator= e2->complex_value.real*e2->complex_value.real+
                                         e2->complex_value.imag*e2->complex_value.imag;
                     
                      if (denominator==0.0)
                         yyerror("Division by zero");
                      
                      ev->type=COMPLEX;
                      ev->complex_value.real=(e1->complex_value.real*e2->complex_value.real)/denominator;
                      ev->complex_value.imag=(-e1->complex_value.real*e2->complex_value.imag)/denominator;
	              break;
                }
        	case REAL:
		      if (e2->real_value.real==0)
     		          yyerror("Division by zero");

                      ev->type=REAL;
                      ev->real_value.real=e1->real_value.real/e2->real_value.real;
	              break;
	   }
           break;
   }

   return ev;
}

/* Funkcija pronalazi realni deo date vrednosti izraza */
EXPRESSION_VALUE* real_part(EXPRESSION_VALUE* e)
{   EXPRESSION_VALUE* ev=(EXPRESSION_VALUE*)malloc(sizeof(EXPRESSION_VALUE));
    ev->type=REAL;
    switch(e->type)
    {    case REAL:
	    ev->real_value.real=e->real_value.real;
         case COMPLEX:
    	    ev->real_value.real=e->complex_value.real;
    }
    return ev;
}

/* Funkcija pronalazi kompleksni deo date vrednosti izraza */
EXPRESSION_VALUE* imag_part(EXPRESSION_VALUE* e)
{   EXPRESSION_VALUE* ev=(EXPRESSION_VALUE*)malloc(sizeof(EXPRESSION_VALUE));
    ev->type=REAL;
    switch(e->type)
    {    case REAL:
	    ev->real_value.real=0.0;
         case COMPLEX:
    	    ev->real_value.real=e->complex_value.imag;
    }
    return ev;
}
 

             /* FUNKCIJE ZA RAD SA DRVETOM PROMENJIVIH */


/* Funkcija postavlja vrednost promenjive u datom cvoru drveta 
   na datu vrednost ukoliko to tipovi dozvoljavaju. 
   Ukoliko vrednost nije definisana postalvlja se na podrazumevanu. */
void SetVariableValue(NODE* variable, EXPRESSION_VALUE* value)
{   switch(variable->type)
    {   case REAL:
             variable->value->type=REAL;
	     if (value==NULL)
	     {  variable->value->real_value.real=0.0;
	        return;
	     }
	     switch(value->type)
	     {     case REAL: 
		     variable->value->real_value.real=value->real_value.real;
                     break;
       	           case COMPLEX:
                     yyerror("Trying to set complex vale for real variable %s\n",variable->name);
		     break;
             }
	     break;

        case COMPLEX:  
             variable->value->type=COMPLEX;
	     if (value==NULL)
	     {  variable->value->complex_value.real=0.0;
       	        variable->value->complex_value.imag=0.0;
	        return;
	     }
	     switch(value->type)
	     {     case REAL: 
                     variable->value->complex_value.real=value->real_value.real;
                     variable->value->complex_value.imag=0.0;
                     break;
       	           case COMPLEX:
                     variable->value->complex_value.real=value->complex_value.real;
                     variable->value->complex_value.imag=value->complex_value.imag;
		     break;
             }
	     break;
    } 
}


/*   Funkcija pronalazi vrednost promenjive u drvetu promenjivih  
     Argumenti 
          tree - pokazivac na koren drveta promenjivih 
          variable_name - ime promenjive 
*/
EXPRESSION_VALUE* FindVariableValue(NODE* tree, char* variable_name)
{   int cmp;

    /*  Promenjiva ne postoji u drvetu */
    if (tree==NULL)
    {   yyerror("Variable %s is not declared \n",variable_name); 
        return NULL;
    }
   
    /* Leksikografski poredimo ime trazene promenive i promennjive u 
       tekucem cvoru drveta */
    cmp=strcmp(variable_name,tree->name);

    /* Pronasli smo promenjivu i vracamo njenu vrednost */
    if (cmp==0)
         return tree->value;

    /* Pretrazujemo levo odnosno desno poddrvo */
    if (cmp<0)
      return FindVariableValue(tree->left, variable_name);
    else
      return FindVariableValue(tree->right, variable_name);

}


/* Funkcija dodaje promenjivu u drvo i postavlja joj vrednost na datu vrednost 
   Argumenti su :
        tree - pokazivac na koren drveta promenjivih 
        variable_name - ime promenjive koja se dodaje 
        type - tip promenjive koja se dodaje
        value - vrednost promenjive koja se dodaje 
                (ukoliko je NULL vrednost se postavlja na podrazumevanu)
*/
        
void AddVariable(NODE** tree, char* variable_name, expression_type type, EXPRESSION_VALUE* value)
{   int cmp;
    
    /* Dodajemo promenjivu kao list drveta */ 
    if ((*tree)==NULL)
    {   *tree=(NODE*)malloc(sizeof(NODE));
        (*tree)->left=NULL;
        (*tree)->right=NULL;
        (*tree)->name=variable_name;
        (*tree)->type=type;
	(*tree)->value=(EXPRESSION_VALUE*)malloc(sizeof(EXPRESSION_VALUE));
        
        /* Postavljamo vrednost promenjive koristeci posebnu funkciju za to namenjenu */
        SetVariableValue(*tree,value);
        return;
    }

   
    /* Leksikografski poredimo ime trazene promenive i promennjive u 
       tekucem cvoru drveta */
    cmp=strcmp(variable_name,(*tree)->name);
  
    /* Promenjiva vec postoji */
    if (cmp==0)
    {   yyerror("Variable %s already declared", variable_name);
        return;
    }

    /* Pretrazujemo levo odnosno desno poddrvo */
    if (cmp<0)
      AddVariable(&((*tree)->left), variable_name, type, value);
    else
      AddVariable(&((*tree)->right),variable_name, type, value);
}

/*  Funkcija pronalazi promenjivu sa datim imenom i pokusava da joj postavi vrednost na datu
    Argumenti su :
        tree - pokazivac na koren drveta promenjivih
        variable_name - ime promenjive koju trazimo 
        value - vrednost promenjive koju postavljamo
 */
void FindVariableAndSetItsValue(NODE* tree, char* variable_name, EXPRESSION_VALUE* value)
{   int cmp;

    /* Promenjiva ne postoji u drvetu */ 
    if (tree==NULL)
    {   yyerror("Variable %s not declared\n",variable_name); 
        return;
    }

    /* Leksikografski poredimo ime trazene promenive i promennjive u 
       tekucem cvoru drveta */
    cmp=strcmp(variable_name, tree->name);
    
   
    /* Postavljamo vrednost promenjive koristeci posebnu funkciju za to namenjenu */
    if (cmp==0)
    {  SetVariableValue(tree,value);
       return;
    }

    /* Pretrazujemo levo odnosno desno poddrvo */
    if (cmp<0)
      FindVariableAndSetItsValue(tree->left,variable_name,value);
    else
      FindVariableAndSetItsValue(tree->right,variable_name,value);
}


/* Funkcija ispisuje sve promenjive u datom drvetu promenjivih */
void PrintTree(NODE* tree)
{   if (tree==NULL)
       return;
    printf("%s : ",tree->name);
    Print(tree->value);
    printf("\n");
    PrintTree(tree->left);
    PrintTree(tree->right);   
}


/* Funkcija uklanja dato drvo promenjivih */
void DeleteTree(NODE* tree)
{   if (tree==NULL)
          return;
    free(tree->name); 
    free(tree->value);
    DeleteTree(tree->left);
    DeleteTree(tree->right);    

}

/* Glavni program */
main()
{   /* Vrsimo parsiranje ulaza */
    yyparse();
 
    /* Stampamo vrednosti svih promenjivih */
    PrintTree(tree);
   
    /* Uklanjamo drvo promenjivih */
    DeleteTree(tree);
}
