/*
    Strukture podataka i algoritmi

    Filip Niksic, 04-0205

    Zadatak 31. Implementirajte a.t.p. BTREE pomocu pointera i napisite
    potprogram koji aritmeticki izraz iz infix oblika prebacuje u postfix
    oblik pomocu binarnog stabla.
*/

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

typedef char *labeltype;

typedef struct celija__ {
    labeltype label;
    struct celija__ *parent;
    struct celija__ *leftchild;
    struct celija__ *rightchild;
} celija;

typedef celija *node;
typedef celija *BTREE;

int EMPTY(BTREE T) {
    /* Vraca "istinu" ako je T prazno stablo. */
    if (T==NULL) return 1;
    else return 0;
}

void MAKE_NULL(BTREE *T) {
    /* Inicijaliziramo stablo. */
    *T=NULL;
}

void DELETE_TREE(BTREE *T) {
    /* Ako je stablo vec prazno, ne radi nista. */
    if (EMPTY(*T)) return;
    
    /* Prvo isprazni lijevo i desno podstablo. */
    if ((*T)->leftchild!=NULL) DELETE_TREE(&((*T)->leftchild));
    if ((*T)->rightchild!=NULL) DELETE_TREE(&((*T)->rightchild));
    
    /* Obrisi cvor iz memorije. */
    free((*T)->label);
    free(*T);
}

void CREATE(labeltype l, BTREE TL, BTREE TR, BTREE *T) {
    *T=(celija *)malloc(sizeof(celija));
    if (*T!=NULL) {
	(*T)->label=(char *)malloc(sizeof(char)*(strlen(l)+1));
	strcpy((*T)->label,l);
	(*T)->parent=NULL;
	(*T)->leftchild=TL;
	(*T)->rightchild=TR;
    }
}

void LEFT_SUBTREE(BTREE T, BTREE *TL) {
    if (!EMPTY(T)) *TL=T->leftchild;
}

void RIGHT_SUBTREE(BTREE T, BTREE *TR) {
    if (!EMPTY(T)) *TR=T->rightchild;
}

node ROOT(BTREE T) {
    return T;
}

/* Pomocna funkcija - vraca "istinu" akko je cvor i u stablu T. */
int INTREE(node i, BTREE *T) {
    while (i!=NULL) {
	if (i->parent==*T) return 1;
	i=i->parent;
    }
    return 0;
}

node INSERT_LEFT_CHILD(labeltype l, node i, BTREE *T) {
    node temp;
    
    if (i==NULL || i->leftchild!=NULL || !INTREE(i,T)) return NULL;

    temp=(celija *)malloc(sizeof(celija));
    if (temp!=NULL) {
	temp->label=(char *)malloc(sizeof(char)*(strlen(l)+1));
	strcpy(temp->label,l);
	temp->parent=i;
	temp->leftchild=NULL;
	temp->rightchild=NULL;
	i->leftchild=temp;
    }

    return temp;
}

node INSERT_RIGHT_CHILD(labeltype l, node i, BTREE *T) {
    node temp;
    
    if (i==NULL || i->rightchild!=NULL || !INTREE(i,T)) return NULL;

    temp=(celija *)malloc(sizeof(celija));
    if (temp!=NULL) {
	temp->label=(char *)malloc(sizeof(char)*(strlen(l)+1));
	strcpy(temp->label,l);
	temp->parent=i;
	temp->leftchild=NULL;
	temp->rightchild=NULL;
	i->rightchild=temp;
    }

    return temp;
}

node PARENT(node i, BTREE T) {
    return i->parent;
}

node LEFT_CHILD(node i, BTREE T) {
    return i->leftchild;
}

node RIGHT_CHILD(node i, BTREE T) {
    return i->rightchild;
}

void DELETE(node i, BTREE *T) {
    if (i==NULL || i->leftchild!=NULL || i->rightchild!=NULL || !INTREE(i,T)) return;

    /* Obavjestavamo roditelja da mu je dijete ubijeno. :-) */
    if (i->parent!=NULL) {
	if (i==i->parent->leftchild) i->parent->leftchild=NULL;
	else i->parent->rightchild=NULL;
    }

    free(i->label);
    free(i);
}

labeltype LABEL(node i, BTREE T) {
    return i->label;
}

void CHANGE_LABEL(labeltype l, node i, BTREE *T) {
    if (i==NULL || !INTREE(i,T)) return;

    i->label=(char *)realloc(i->label,sizeof(char)*(strlen(l)+1));
    strcpy(i->label,l);
}

/*
    Funkcija koja rastavlja aritmeticki izraz i slaze ga u stablo.
    
    Ideja je sljedeca: Pronadjemo operator s najnizim prioritetom i
    rekurzivno pozivamo funkciju za ostatak izraza lijevo od
    operatora i ostatak desno od operatora. Stablo formiramo tako
    da mu za oznaku stavimo operator, lijevo podstablo se formira
    od lijevog ostatka, a desno se formira od desnog ostatka.
*/
BTREE parse(char *izraz, int len) {
    BTREE left,right,temp;
    int i,j=-1,zagrada=0;
    char znak;
    
    /* Eliminacija zagrada. */
    if (izraz[0]=='(' && izraz[len-1]==')') return parse(izraz+1,len-2);

    /*
	Pronalazimo operator s najnizim prioritetom. Moramo paziti
	da bude izvan zagrada. Takodjer, pazimo koji operator uzimamo
	u slucaju vise njih (neke operacije nisu komutativne).
    */
    for (i=0;i<len;i++)
	switch (izraz[i]) {
	    case '(':
		zagrada++;break;
	    case ')':
		zagrada--;break;
	    case '+': case '-':
		if (zagrada==0) j=i;break;
	    case '*': case '/': case '%':
		if (zagrada==0 && (j==-1 || (izraz[j]!='+' && izraz[j]!='-'))) j=i;break;
	    case '^':
		if (zagrada==0 && j==-1) j=i;break;
	    default:
		break;
	}

    MAKE_NULL(&temp);
    MAKE_NULL(&left);
    MAKE_NULL(&right);
    
    if (j==-1) {
	/* Ako operator nije pronadjen, onda je cijeli izraz zapravo operand. */
	znak=izraz[len];
	izraz[len]='\0';
	CREATE(izraz,left,right,&temp);  // left i right su prazna stabla
	izraz[len]=znak;
    }
    else {
	/*
	    Rekurzivno formiramo lijevo i desno podstablo i spajamo ih s operatorom
	    kao korijenom.
	*/
	left=parse(izraz,j);
	right=parse(izraz+j+1,len-j-1);
	znak=izraz[j+1];
	izraz[j+1]='\0';
	CREATE(izraz+j,left,right,&temp);
	izraz[j+1]=znak;
    }

    return temp;
}

/* Rekurzivan POSTORDER obilazak stabla. */
void ispisi(BTREE T) {
    BTREE temp;
    node r;
    
    MAKE_NULL(&temp);
    
    if (!EMPTY(T)) {
	/* Ispisujemo lijevo podstablo. */
	LEFT_SUBTREE(T,&temp);
	ispisi(temp);
	/* Ispisujemo desno podstablo. */
	RIGHT_SUBTREE(T,&temp);
	ispisi(temp);
	/* Ispisujemo korijen. */
	r=ROOT(T);
	printf("%s ",LABEL(r,T));
    }
}

int main(void) {
    char izraz[1024];
    BTREE stablo;
    
    printf("Prebacivanje aritmetickog zapisa iz infix oblika u postfix oblik.\n\n");
    printf("Znakovi koji se tretiraju kao operatori (po prioritetu od najnizeg):\n");
    printf("    + -\n    * / %%\n    ^\n");
    printf("Oble zagrade () se tretiraju standardno.\n");
    printf("Svi ostali znakovi se tretiraju kao operandi. Za unos se ocekuje ispravan\n");
    printf("aritmeticki izraz.\nZa kraj treba upisati KRAJ.\n");
    
    while (1) {
	printf("\nUnesi izraz: ");
	scanf("%s",izraz);

	if (strcmp(izraz,"KRAJ")==0) break;
	
	/* Poziv funkcije koja pretvara izraz u stablo. Ovdje je vecina magije. */
	stablo=parse(izraz,strlen(izraz));
	
	printf("Postfix: ");
	ispisi(stablo);
	printf("\n");
	
	DELETE_TREE(&stablo);
    }
    
    return 0;
}