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

// les listes
typedef struct sliste
{
  int char_ou_entier;
  int lv;
  char lc;
  struct sliste *suiv;
} *LISTE, liste;

liste *lvide()
{
  return NULL;
}

liste *adj_tete_entier(int el, liste *l)
{
  liste *element = (liste *)malloc(sizeof(liste));
  element->char_ou_entier=0;
  element->lv=el;
  element->suiv=l;
  return element;

}

liste *adj_tete_char(char el, liste *l)
{
  liste *element = (liste *)malloc(sizeof(liste));
  element->char_ou_entier=1;
  element->lc=el;
  element->suiv=l;
  return element;
}

liste *queue(liste *l)
{
  return l->suiv;
}

void aff_liste(liste *l)
{
  if (l==NULL)
    {
      printf("vide\n");
    }
  else
    {
      if (l->char_ou_entier==1)
	printf("%c ", l-> lc);
      else printf("%d ", l->lv);
      aff_liste(l->suiv);

    }
}

// les piles
typedef struct spile
{
  int pv;
  struct spile *suivant;
} *PILE, pile;

pile *pvide()
{
  return NULL;
}

pile *empiler(pile *p, int x)
{
  pile *element = (pile *)malloc(sizeof(pile));
  element->pv=x;
  element->suivant=p;
  return element;
			       
}

pile *depiler(pile *p)
{
  return (p->suivant);
}

int sommet(pile *p)
{
  return(p->pv);
}


int eval_postfixe(liste *l, pile *p)
{
  if (l==NULL)
    {
      if ((p!=NULL) && (p->suivant==NULL))
	return (sommet(p));
      else 
	{
	  printf("erreur\n"); 
	  exit(2);
	}
    }

  if (l->char_ou_entier==1)
    {       // char
      
      int v1 = sommet(p);
      int v2=sommet(depiler(p));
      if (l->lc=='+')
	{
	return eval_postfixe(queue(l), empiler (depiler(depiler(p)), v1+v2));
	}
      else 
	if (l->lc=='-')
	  {
	    return eval_postfixe(queue(l), empiler (depiler(depiler(p)), v2-v1));
	  }

	else
	  if (l->lc=='*')
	    {
	      return eval_postfixe(queue(l), empiler (depiler(depiler(p)), v1*v2));
	    }
	  else
	    
	{
	  printf("unexpected char : %cn",l->lc);
	  exit(3);
	}
    }
  else
    {
      // entier
      return (eval_postfixe(queue(l), empiler(p, l->lv)));
    }
}

liste *analyse_chaine(char *tmp, int pos, int acc)
{
  //  printf("char tmp [%d]=%c\n" , pos, tmp[pos]);
  if (tmp[pos]=='\0')
    return lvide();
  
  if (tmp[pos]>'0' && tmp[pos]<'9') 
    return (analyse_chaine(tmp, pos+1, 10*acc +(tmp[pos]-'0')));
  
  if (tmp[pos]==' ')
    {
      if (acc!=0)
	return (adj_tete_entier(acc, analyse_chaine(tmp, pos+1, 0)));
      else 
	return analyse_chaine(tmp, pos+1, 0);
    }
  
  if((tmp[pos]=='+')||(tmp[pos]=='-')||(tmp[pos]=='*'))
    {
      if (acc!=0) 
	return(adj_tete_entier(acc, adj_tete_char(tmp[pos], analyse_chaine(tmp, pos+1, 0))));
      else
	return (adj_tete_char(tmp[pos], analyse_chaine(tmp, pos+1, 0)));
    }
  else {printf("unexpected char %c\n", tmp[pos]); exit(3);}
}


int main(int argc, char *argv[])
{
  // exemple a tester ./c "4 2*7+3*2 3++" -> 50
  char tmp[200];
  int i;
  int v=0;
  liste *test = adj_tete_entier (2, adj_tete_entier (12, adj_tete_char ('-', lvide())));
  liste *l;
  if (argc!=2) {printf("usage : %s <string>\n", argv[0]); exit(1);}
  printf("test 1 : %d\n", eval_postfixe(test, pvide()));
  printf("\nTest sur la chaine recue\n");
  strcpy(tmp, argv[1]);

  printf("chaine recue : |%s|\n", tmp);
  l= analyse_chaine(tmp, 0, 0);
  printf("liste representant la chaine : ");
  aff_liste(l);
  printf("resultat du calcul : %d\n", eval_postfixe(l, pvide()));

  return 0;
}
