/*
    Filip Niksic
    04-0205

    Rjesenje zadatka s izvanrednog kolokvija 8.4.2006. iz RP1.
*/

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

#define maxline 1024

typedef struct cvor__ {
    char p,k;
    struct cvor__ *left,*right,*parent;
} cvor;

/* Stablo poistovijetimo s pointerom na korijen. */
cvor *root;

/* Ovo se koristi pri konstrukciji stabla. */
int indeks;
char linija[maxline],S[maxline];

/* Funkcija koja dovodi vrijednost a->p u root->p. */
void postavi(cvor *a) {
    char temp;
    
    while (a->parent!=NULL) {
	printf("SWAP(%c,%c)\n",a->parent->p,a->p);
	temp=a->parent->p;
	a->parent->p=a->p;
	a->p=temp;
	
	a=a->parent;
    }
}

/* Funkcija koja dohvaca vrijednost iz root->p. */
void dohvati(cvor *a) {
    char temp;

    if (a->parent!=NULL) {
	dohvati(a->parent);
	printf("SWAP(%c,%c)\n",a->parent->p,a->p);
	temp=a->parent->p;
	a->parent->p=a->p;
	a->p=temp;
    }
}

/* Funkcija locira cvor u stablu koji ima vrijednost v. */
cvor *lociraj(cvor *bla,char v) {
    cvor *pronadjen;
    
    if (bla==NULL) return NULL;
    
    /* Provjerimo jesmo li nasli v. */
    if (bla->p==v) return bla;

    /* Mislim da je pametnije prvo pretraziti desno podstablo. */
    pronadjen=lociraj(bla->right,v);

    /* Ako ga nismo pronasli, trazimo u lijevom podstablu. */
    if (pronadjen!=NULL) return pronadjen;
    else return lociraj(bla->left,v);
}

void sredi(cvor *bla) {
    if (bla!=NULL) {
	/* Prvo sredimo lijevo i desno podstablo */
	sredi(bla->left);
	sredi(bla->right);

	/* Zatim sredimo i trenutni cvor */
	if (bla->p!=bla->k) {
	    postavi(lociraj(root,bla->k));
	    dohvati(bla);
	}
    }
}

/* Pomocna funkcija za ispis stabla u prefixu. */
void preorder(cvor *bla) {
    if (bla!=NULL) {
	printf("(%c,%c)",bla->p,bla->k);
	preorder(bla->left);
	preorder(bla->right);
    }
}

cvor *konstruiraj(void) {
    cvor *temp;
    
    /* Do ovog ne bi ni trebalo doci. */
    if (linija[indeks]=='\0') return NULL;
    
    if (linija[indeks]!='*') {
	temp=(cvor *)malloc(sizeof(cvor));
	temp->p=linija[indeks++];
	temp->k='#';
	temp->left=konstruiraj();
	temp->right=konstruiraj();
	temp->parent=NULL;
	
	/* Novostvorenu djecu naucimo tko im je roditelj. */
	if (temp->left!=NULL) temp->left->parent=temp;
	if (temp->right!=NULL) temp->right->parent=temp;

	return temp;
    }
    else {
	indeks++;
	return NULL;
    }
}

void dodaj_konacno(cvor *bla) {
    if (bla!=NULL) {
	bla->k=S[indeks++];
	dodaj_konacno(bla->left);
	dodaj_konacno(bla->right);
    }
}

void obrisi_stablo(cvor *bla) {
    if (bla!=NULL) {
	obrisi_stablo(bla->left);
	obrisi_stablo(bla->right);
	free(bla);
    }
}

int main(int argc,char *argv[]) {
    FILE *in;

    if ((in=fopen(argv[1],"r"))==NULL) {
	printf("Grjeska prilikom otvaranja datoteke %s!\n",argv[1]);
	return 1;
    }
    fscanf(in,"%s%s",linija,S);
    fclose(in);

    /* Napravimo pocetno stablo. */
    indeks=0;
    root=konstruiraj();

    // preorder(root);printf("\n");
    
    /* Dodamo konacno stablo. */
    indeks=0;
    dodaj_konacno(root);

    sredi(root);

    // preorder(root);printf("\n");

    obrisi_stablo(root);

    return 0;
}