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

#define VAR 0
#define NO 1
#define OP 2

typedef struct _cvor
{
		int br;
		char sgn;
		int type;
		struct _cvor *left,*right;
} cvor;

cvor* makeNode();
cvor* strToTree(char**);
cvor* strToTree2(char**);
void treePrint(cvor*);
void clearTree(cvor*);
int getVal(int,cvor*);

int main(int argc,char *argv[])
{
	 char s[80],*p;
	 int x;
	 cvor* koren;
	 printf("Unesite izraz:\n");
	 fgets(s,80,stdin);
	 p = s;
	 koren = strToTree(&p);
	 putchar('\n');
	 printf("Unesite vrednost x za koju zelite izracunati izraz:");
	 scanf("%d",&x);
	 printf("Za x = %d: ",x);
	 treePrint(koren);
	 printf("=%d\n",getVal(x,koren));
	 clearTree(koren);
}

cvor* makeNode()
{
	cvor *novi= (cvor*)malloc(sizeof(cvor));
	if(!novi)
	{
		fprintf(stderr,"Greska pri alokaciji memorije");
		exit(1);
	}
	novi->left = NULL;
	novi->right = NULL;
	return novi;
}

cvor* strToTree(char** s)
{
	  cvor* novi= makeNode();
	  
	   /*preskacemo beline ako postoje na pocetku stringa*/
	  if(**s==' ')
		while(*(++(*s))==' ');

	  /*ako je broj generisemo ga i pravimo list*/
	  if(**s >= '0' && **s <='9')
	  {
	  	int n=0;
	   	while((**s >= '0') && (**s < '9') )
			 n = n*10 + (*((*s)++) - '0');
		novi->type = NO;
		novi->br = n;
          /*nema potrebe za pomeranjem pokazivaca posto je to odrajeno u petlji*/
	  }
	  /*ako je promenljiva postavljamo list i flag za list*/
	  else if(**s == 'x')
	  {
	  	novi->sgn = 'x';
	    	novi->type = VAR;
	    	(*s)++;
	  }
	  /*inace je operator*/
	  else
	  {
	  	novi->sgn = **s;
	  	novi->type = OP;
		(*s)++;
	  	novi->left = strToTree(s);
	  	novi->right = strToTree(s);
	  }
	  return novi;
}

cvor* strToTree2(char** s)
{
	  cvor* novi= makeNode();
	  
	   /*preskacemo beline ako postoje na pocetku stringa*/
	  if(**s==' ')
		while(*(++(*s))==' ');

	  /*stavljamo znak u cvor*/
	  novi->sgn = **s;
	  novi->type = OP;
	  
	  /*preskacemo beline*/
	  while(*(++(*s)) ==' ');

	  /*proveravamo da li je prvi argument promenljiva*/
	  if(**s == 'x')
	  {
	    cvor* left = makeNode();
	    novi->left = left;
	    left->sgn = 'x';
	    left->type = VAR;
	  }
     /*proveravmo da li je broj sledeci argument, ako jeste */
	  /*nalazimo ga i pravimo levi list */
	  else if((**s >= '0') && (**s <= '9'))
	  {
	   int n=0;
	   cvor* left = makeNode();
	   novi->left = left;
	   while((**s >= '0') && (**s < '9') )
		 n = n*10 + (*((*s)++) - '0');
	   left->type = NO;
	   left->br = n;
	  }
     /*ako nije broj onda je znak /* + -, pod pretpostavkom da je */
	  /*iraz tacno unet */
	  else
	  novi->left = strToTree(s);

	  /*preskacemo beline*/
	  while(*(++(*s))==' ');

     /*proveravamo da li je drugi argument promenljiva*/
	  if(**s == 'x')
	  {
	    cvor* right = makeNode();
	    novi->right = right;
	    right->sgn = 'x';
	    right->type = VAR;
	  }

     /*proveravmo da li je broj sledeci argument, ako jeste */
	  /*nalazimo ga i pravimo desni list */

	  else if(**s >= '0' && **s <= '9' )
	  {
	   int n=0;
	   cvor* right = makeNode();
	   novi->right = right;
	   while((**s > '0') && (**s < '9') )
		   n = n*10 + (*((*s)++) - '0');
	   right->type = NO;
	   right->br = n;
	  }
	       /*ako nije broj onda je znak /* + -, pod pretpostavkom da je */
					  /*iraz tacno unet */
	  else
			novi->right = strToTree(s);
	  return novi;
}

void treePrint(cvor* koren)
{
	if(!koren)
		return;
	switch(koren->type)
	{
		case OP:
		{
			putchar('(');
			treePrint(koren->left);
			putchar(koren->sgn);
			treePrint(koren->right);
			putchar(')');
		break;
		}
		case VAR:
		{
			putchar(koren->sgn);
			break;
		}
		case NO:
		{
			printf("%d",koren->br);
			break;
		}
	}
}

void clearTree(cvor* koren)
{
	if(koren)
	{
		clearTree(koren->left);
		clearTree(koren->right);
		free(koren);
	}
}

int getVal(int x,cvor* koren)
{
	switch(koren->type)
	{
		case NO:
			return koren->br;
		case VAR:
			return x;
		case OP:
			switch(koren->sgn)
			{
				case '+':
					return getVal(x,koren->left) + getVal(x,koren->right);
				case '-':
					return getVal(x,koren->left) - getVal(x,koren->right);
				case '/':
					return getVal(x,koren->left) / getVal(x,koren->right);
				case '*':
					return getVal(x,koren->left) * getVal(x,koren->right);
			}
	}
}