/* Datoteka : citljivi_izrazi.y */
%{
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/* Izraze delimo na elementarne (promenjive i konstante)
   aditivne (na "vrhu" je + ili -) i
   multiplikativne (na "vrhu" je * ili /) */
enum {ELEMENT, ADITIVNA, MULTIPLIKATIVNA};

/* Svakom izrazu odgovara matrica karaktera.
   Posto ne znamo kolike ove matrice mogu biti pravimo
   ih dinamickim */

typedef struct _mat
{  char **mat;
   int bv,bk;

   /* Vrsta matrice u kojoj se nalazi glavna
      razlomacka crta */
   int raz_crta;

   /* Zbog pravilnog postavljanja zagrada potrebno je
      znati i vrstu operacije na "vrhu" izraza */
   int vrsta_operacije;
} matrica;

/* Na atributski stek cemo stavljati pokazivace
   na matrice karaktera koje odgovaraju izrazima */
#define YYSTYPE matrica*

/* Funkcija za obradu greske */
#define yyerror printf

/* Lex promenjiva koja ukazuje na tekucu leksemu */
extern char* yytext;

/* Maksimum dva broja */
#define max(a,b) ((a>b)?(a):(b))
%}

%left '+','-'
%left '*','/'
%token LITERAL,'(',')'

%%

pocetak : izraz { ispisi($1); oslobodi($1);}

izraz : izraz '+' izraz
        { $$=matrica_pored_matrice($1,'+',$3);
          oslobodi($1);
          oslobodi($3);}
      | izraz '-' izraz
         {$$=matrica_pored_matrice($1,'-',$3);
         oslobodi($1);
         oslobodi($3);}
      | izraz '*' izraz
     {$$=matrica_pored_matrice($1,'*',$3);
      oslobodi($1);
      oslobodi($3);}
      | izraz '/' izraz
     {$$=matrica_iznad_matrice($1,$3);
      oslobodi($1);
      oslobodi($3);}
      | '(' izraz ')'
         {$$=$2;}
      | LITERAL
         { $$=napravi_matricu(yytext); }
      ;

%%

/* Funkcija alocira memoriju za matricu koja ima
   bv vrsta i bk kolona */
matrica* alociraj(int bv, int bk)
{   int i,j;
    matrica* pm=(matrica*) malloc(sizeof(matrica));
    pm->bv=bv;
    pm->bk=bk;
    pm->mat=(char**) malloc(bv*sizeof(char*));
    for (i=0; i<bv; i++)
    {  pm->mat[i]=(char*) malloc(bk*sizeof(char));
       for (j=0; j<bk; j++)
          pm->mat[i][j]=' ';
    }
    pm->raz_crta=0;
    pm->vrsta_operacije=ELEMENT;
    return pm;
}

/* Ispisuje se matrica karaktera */
void ispisi(matrica* pm)
{   int i,j;
    for (i=0; i<pm->bv; i++)
    {   for (j=0; j<pm->bk; j++)
           printf("%c",pm->mat[i][j]);
        printf("\n");
    }
}


/* Oslobadjamo strukturu matrice */
void oslobodi(matrica* pm)
{   int i,j;
    for (i=0; i<pm->bv; i++)
       free(pm->mat[i]);
    free(pm->mat);
    free(pm);
}

/* Pravimo "elementarnu" matricu na osnovu
   niza karaktera */
matrica* napravi_matricu(char* lit)
{   matrica *pm;
    pm=(matrica*) malloc(sizeof(matrica));
    if (pm==NULL)
    {   yyerror("Greska : neuspesno alociranje memorije ");
        exit(1);
    }
    pm->bv=1;
    pm->bk=strlen(lit);
    pm->mat=(char**) malloc(sizeof(char*));
    pm->mat[0]=strdup(lit);
    pm->raz_crta=0;
    pm->vrsta_operacije=ELEMENT;
    return pm;
}

/* Funkcija ubacuje blok matricu s u matricu d i to tako
   da gornji levi ugao bude na poziciji x,y matrice d */
void ubaci_mat_u_mat(matrica* d, matrica* s, int x, int y)
{   int i,j;
    for (i=0; i<s->bv; i++)
       for(j=0; j<s->bk; j++)
          d->mat[x+i][y+j]=s->mat[i][j];
}

/* Gradimo novu matricu tako sto postavljamo matricu l,
   zatim operator i onda matricu d jedno pored drugoga */
matrica* matrica_pored_matrice(matrica* l, char op, matrica* d)
{  int bv,bk;
   int bordura,zagrade_levo,zagrade_desno;
   int sirina_levog, sirina_desnog,
       pocetak_levog, kraj_levog,
       pocetak_desnog, kraj_desnog;
   matrica* pm;

   /* Ako matrice l i d sadrze razlomacku crtu ostavljamo
      jedno prazno mesto izmedju razlomaka i operatora */
   bordura=(l->raz_crta==0 &&
            d->raz_crta==0)?0:1;

   /* Da li ima potrebe stavljati matricu l u zagrade ? */
   zagrade_levo=((op=='*') && (l->vrsta_operacije==ADITIVNA))?1:0;

   /* Da li ima potrebe stavljati matricu d u zagrade ? */
   zagrade_desno=(((op=='*') && (d->vrsta_operacije==ADITIVNA)) ||
                 ((op=='-') && (d->vrsta_operacije==ADITIVNA)))?1:0;

   /* sirina_operanada ukljucujuci i zagrade*/
   sirina_levog  = zagrade_levo  + l->bk + zagrade_levo;
   sirina_desnog = zagrade_desno + d->bk + zagrade_desno;

   /* Pozicija na kojoj pocinji i zavrsavaju se operandi
      (ne racunajuci zagrade)*/
   pocetak_levog  = 0;
   kraj_levog     = zagrade_levo + l->bk;
   pocetak_desnog = sirina_levog+bordura+1+bordura;
   kraj_desnog    = pocetak_desnog+zagrade_desno+d->bk;

   /* Odredjujemo dimenzije nove matrice */
   bk=sirina_levog+
      bordura+1+bordura+
      sirina_desnog;

   bv=max(l->raz_crta,d->raz_crta)+
      1+
      max(l->bv-l->raz_crta-1,d->bv-d->raz_crta-1) ;

   /* Alociramo prostor */
   pm=alociraj(bv,bk);
   /* Odredjujemo polozaj glavne razlomacke crte */
   pm->raz_crta=max(l->raz_crta,d->raz_crta);

   /* Postavljamo polja strukture */
   pm->vrsta_operacije=(op=='*')?MULTIPLIKATIVNA:ADITIVNA;

   /* Operator postavljamo na odgovarajuce mesto */
   pm->mat[pm->raz_crta][sirina_levog+bordura]=op;
   /* Ukoliko je potrebno staviti zagrade postavljamo ih */
   if (zagrade_levo)
   {   pm->mat[pm->raz_crta][pocetak_levog]='(';
       pm->mat[pm->raz_crta][kraj_levog]=')';
   }

   if (zagrade_desno)
   {  pm->mat[pm->raz_crta][pocetak_desnog]='(';
      pm->mat[pm->raz_crta][kraj_desnog]=')';
   }
   /* Ugradjujemo vec postojece matrice l i d na odgovarajuce pozicije */
   ubaci_mat_u_mat(pm,l,pm->raz_crta-l->raz_crta,
                   pocetak_levog+zagrade_levo);
   ubaci_mat_u_mat(pm,d,pm->raz_crta-d->raz_crta,
                   pocetak_desnog+zagrade_desno);

   return pm;
}

/* Gradimo razlomak od dve matrice */
matrica* matrica_iznad_matrice(matrica* l, matrica* d)
{  int bv,bk,bordura;
   int i;
   matrica* pm;

   /* Ukoliko je ili brojilac ili imenilac razlomak,
      onda razlomacka crta mora biti duza */
   bordura=(l->raz_crta==0 &&
            d->raz_crta==0)?0:1;

   /* Odredjujemo broj vrsta i kolona nove matrice */
   bk=max(l->bk,d->bk)+2*bordura;
   bv=l->bv+1+d->bv;

   /* Alociramo memoriju */
   pm=alociraj(bv,bk);

   /* Ubacujemo brojilac */
   ubaci_mat_u_mat(pm,l,0,(bk-l->bk)/2);

   /* Gradimo razlomacku crtu */
   for (i=0; i<bk; i++)
     pm->mat[l->bv][i]='-';

   /* Ubacujemo imenilac */
   ubaci_mat_u_mat(pm,d,l->bv+1,(bk-d->bk)/2);

   /* Postavljamo ostala polja strukture */
   pm->raz_crta=l->bv;
   pm->vrsta_operacije=MULTIPLIKATIVNA;
   return pm;
}

main()
{  yyparse();
}
