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

/*******************************
*  Gramatika je:
*  E -> E+T
*	|T
*  T -> T*F
*	|F
*  F => (E)
*	|num
*  Moramo se obavezno osloboditi leve rekurzije
*  pravila	skupovi izbora
*  E -> TE'	{ num , ( }
*  E'->	+TE'	{ + }
*	|eps	{ ) , EOI }
*  T -> FT'	{ ( , num }
*  T'-> *FT'	{ * }
*	|eps	{ + , ) , EOI }
*  F -> (E)	{ ( }
*	|num	{ num }
*  Uradicemo sintaksnu analizu odozgo nadole, simulaciom potisnog automata
*
*  Za racunanje vrednosti, izraz se prevodi u postfiksnu notaciju,
*  a zatim se putem steka vrednosti sracunava njegova vrednost.
*  Prevodjenje u postfiksnu notaciju se ostvaruje sledecom shemom
*  (u ovom slucaju koristi se leva asocijativnost)
*
*	E  -> T E'	
*	E' -> +T {print(+)} E'	
*	    | eps
*	T  -> F T'
*	T' -> *F {print(*)} T'
*	    | eps
*	F  -> (E)
*	    | num {print(num.v)}	
*
*  Akcije u sredini pravila je moguce osloboditi se koriscenjem 
*  pomocnih neterminala, odnosno sheme
*
*	E  -> T E'	
*	E' -> +T A1 E'	
*	    | eps
*	T  -> F T'
*	T' -> *F A2 T'
*	    | eps
*	F  -> (E)
*	    | num	{print(num.v)}	
*	A1 -> eps 	{print(+)}
*	A2 -> eps	{print(*)}
*
*  Ukoliko se zeli efektivno racunanje vrednosti uvodi se poseban 
*  stek vrednosti i akcije se menjaju u 
*	E  -> T E'	
*	E' -> +T A1 E'	
*	    | eps
*	T  -> F T'
*	T' -> *F A2 T'
*	    | eps
*	F  -> (E)
*	    | num	{push(num.v)}	
*	A1 -> eps 	{a = pop(); b = pop(); push(b+a)}
*	A2 -> eps	{a = pop(); b = pop(); push(b*a)}
*
*
*******************************/

/* Deklarisemo tokene koji nam se javljaju u gramatici */
#define NUM 1
#define PLUS 2
#define ZVEZDA 3
#define OZ 4			/* otvorena zagrada */
#define ZZ 5			/* zatvorena zagrada */
#define EOI 0			/* end of inpit */
/* Pored tokena na steku se mogu naci i nerminal, tako da i njih kodiramo brojevima */
#define E 6
#define EP 7
#define T 8
#define TP 9
#define F 10
#define A1 11
#define A2 12

/* uvodimo sledeci define, samo ako hocemo da nam program ispise izvodjenje, tj. postfiksno ispisivanje */
/* #define ISPIS 1 */
#define ISPIS_POST

/* Spoljasnja promenljiva koja ce predstvljati preduvidni token */
int lookahead;

/* Funkcija za obradu greske */
int
greska (char *poruka)
{
  fprintf (stderr, "%s\n", poruka);
  exit (EXIT_FAILURE);
  return -1;
}


/* Sami cemo isprogramirati leksicki alalizator,
 * a kasnije, u slozenijim primerima cemo koristiti
 * sistem lex. Promenljiva yylval ce sadrzati vrednosti
 * tekuceg tokena ako je on NUM
 */
int yylval;
int
yylex ()
{
  int ch = getchar ();
  switch (ch)
    {
    case '+':
      return PLUS;
    case '*':
      return ZVEZDA;
    case '(':
      return OZ;
    case ')':
      return ZZ;
    case '\n':
    case EOF:
      return EOI;
    }
  /* Ako je procitani karakter cifra, citamo sve naredne karaktere,
   * do pojave necega sto nije cifra, u cilju da procitano broj
   */
  if (isdigit (ch))
    {
      yylval = ch - '0';
      while (isdigit (ch = getchar ()))
	yylval = yylval * 10 + ch - '0';
      /* Ono poslednje sto smo procitali, i sto nije cifra, vracamo na ulaz */
      ungetc (ch, stdin);
      return NUM;

    }
  /* Ako se na ulazu nije pojavilo nista od ovoga, onda prekidamo program,
   * i ispisujemo propratnu poruku
   */
  greska ("Leksicka greska: Nepoznat ulaz");
  return -1;
}

/* Makro za ucitavanje novog preduvidnog tokena u lookahead */
#define advance()   ( lookahead = yylex() )

/* Makro za proveravanje da li je preduvidni token jednak necemu */
#define match(x)    (lookahead == (x))

/* Maksimalna velicina steka potisnog automata,
 * stek cemo predstavljati pomocu statickog niza
 * i pokazivaca na prvo slobodno mesto u nizu */
#define MAX_STACK 256
#define STACK(type, array)	type array[MAX_STACK];\
 				int sp_##array = 0

/* Makroi koji barataju sa stekom */
#define empty(array)	(sp_##array<=0)
#define full(array)	(sp_##array>=MAX_STACK)
#define top(array)	(array[sp_##array - 1])
#define pop(array)	(empty(array)?greska("Stek je prazan"):(array[--sp_##array]))
#define push(array, x)	(full(array)?greska("Stek je pun"):(array[sp_##array++]=(x)))


int
main ()
{
  /* Stek potisnog automata */
  STACK (int, parse_stack);
  /* Stek na kome cuvamo vrednosti */
  STACK (int, value_stack);

  /* Ucitavamo prvi token */
  advance ();

  /* Na stek stavljamo aksiomu gramatike, tj. startni simbol */
  push (parse_stack, E);

  /* Sve dok je stek automata neprazan */
  while (!empty (parse_stack))
    {
      /* gledamo sta je na vrhu steka */
      switch (top (parse_stack))
	{
	  /* ako je na vrhu steka E */
	case E:
	  /* Proveravamo da li je preduvidni token jedan NUM ili ( */
	  if (match (NUM) || match (OZ))
	    {
	      /* ako jeste preduzimamo svodjenje E -> T E'
	       * tj. sa steka skidamo E, a postavljamo T i E',
	       * ali u ubrnutom poretku. Zasto?
	       */
	      pop (parse_stack);
	      push (parse_stack, EP);
	      push (parse_stack, T);
	      /* Ako nam treba najlevlje izvodjenje, ispisujemo ga */
#ifdef ISPIS
	      printf ("E->TE'\n");
#endif
	    }
	  /* u suprotom ispisujemo gresku */
	  else
	    greska ("Sintaksna greska: Na ulazu ocekujemo NUM ili (");
	  break;
	  /* ako je na vrhu steka E' */
	case EP:
	  if (match (PLUS))
	    {
	      /* sa steka skidamo E'
	       * a na stek postavljamo + T A1 E' u obrnutom poretku
	       */
	      pop (parse_stack);
	      push (parse_stack, EP);
	      push (parse_stack, A1);
	      push (parse_stack, T);
	      push (parse_stack, PLUS);
#ifdef ISPIS
	      printf ("E'->+T A1 E'\n");
#endif
	    }
	  else if (match (ZZ) || match (EOI))
	    {
	      /* primenjujemo svodjenje E'->eps
	       * dakle samo sa steka skidamo E'
	       */
	      pop (parse_stack);
#ifdef ISPIS
	      printf ("E'->eps\n");
#endif
	    }
	  else
	    greska
	      ("Sintaksna greska: Na ulazu je ocekivamo + ili ) ili kraj ulaza");
	  break;
	case T:
	  if (match (NUM) || match (OZ))
	    {
	      pop (parse_stack);
	      push (parse_stack, TP);
	      push (parse_stack, F);
#ifdef ISPIS
	      printf ("T->FT'\n");
#endif
	    }
	  else
	    greska ("Sintaksna greska: Na ulazu ocekujemo NUM ili (");
	  break;
	case TP:
	  if (match (ZVEZDA))
	    {
	      pop (parse_stack);
	      push (parse_stack, TP);
	      push (parse_stack, A2);
	      push (parse_stack, F);
	      push (parse_stack, ZVEZDA);
#ifdef ISPIS
	      printf ("T'->* F A2 T'\n");
#endif
	    }
	  else if (match (PLUS) || match (ZZ) || match (EOI))
	    {
	      pop (parse_stack);
#ifdef ISPIS
	      printf ("T'->eps\n");
#endif
	    }
	  else
	    greska
	      ("Sintaksna greska: Ocekivano je na ulazu *, +, ) ili kraj ulaza");
	  break;
	case F:
	  if (match (OZ))
	    {
	      pop (parse_stack);
	      push (parse_stack, ZZ);
	      push (parse_stack, E);
	      push (parse_stack, OZ);
#ifdef ISPIS
	      printf ("F->(E)\n");
#endif
	    }
	  else if (match (NUM))
	    {
	      pop (parse_stack);
	      push (parse_stack, NUM);
#ifdef ISPIS
	      printf ("F->num\n");
#endif

	      /* stavljamo na stek vrednost num-a */
	      push (value_stack, yylval);

	      /* ako hocemo ispis u postfiksnoj notaciji */
#ifdef ISPIS_POST
	      printf ("%d ", yylval);
#endif
	    }
	  else
	    greska ("Sintaksna greska: Ocekivano je na ulazu ( ili num");
	  break;
	case A1:
	  {
	    /* Dve poslednje vrednosti sa steka vrednosti skidamo,
	     * sabiramo ih, i zbir ponovo vracamo na stek
	     */
	    int a, b;
	    a = pop (value_stack);
	    b = pop (value_stack);
	    push (value_stack, a + b);
	    /* Skidamo sa steka automata A1, jer A1->eps */
	    pop (parse_stack);
#ifdef ISPIS
	    printf ("A1->eps\n");
#endif
	    /* Ako hocemo ispis izraza u postfiksnoj notaciji */
#ifdef ISPIS_POST
	    printf ("+ ");
#endif
	    break;
	  }
	case A2:
	  {
	    /* Dve poslednje vrednosti sa steka vrednosti skidamo,
	     * mnozimo ih, i proizvod ponovo vracamo na stek
	     */
	    int a, b;
	    a = pop (value_stack);
	    b = pop (value_stack);
	    push (value_stack, a * b);
	    /* Skidamo sa steka automata A2, jer A2->eps */
	    pop (parse_stack);
#ifdef ISPIS
	    printf ("A2->eps\n");
#endif
	    /* Ako hocemo ispis izraza u postfiksnoj notaciji */
#ifdef ISPIS_POST
	    printf ("* ");
#endif
	  }
	default:
	  /* ako se na vrhu steka nadje nesto sto nije neterminal,
	   * to onda mora da bude terminal(token)
	   * koji mora da se poklapa sa onim sto je preduvidni token
	   */
	  if (match (top (parse_stack)))
	    {
	      /* Skidamo token sa steka, i ucitavamo sledeci token */
	      pop (parse_stack);
	      advance ();
	    }
	  /* ako nam se ne poklapaju vrh steka i preduvidni token, ispisujemo gresku */
	  else
	    {
	      switch (top (parse_stack))
		{
		case NUM:
		  greska ("Sintaksna greska: Ocekivano je na ulazu NUM\n");
		case PLUS:
		  greska ("Sintaksna greska: Ocekivano je na ulazu +");
		case ZVEZDA:
		  greska ("Sintaksna greska: Ocekivano je na ulazu *");
		case OZ:
		  greska ("Sintaksna greska: Ocekivano je na ulazu (");
		case ZZ:
		  greska ("Sintaksna greska: Ocekivano je na ulazu )");
		case EOI:
		  greska ("Sintaksna greska: Ocekivano je kraj ulaza");
		}
	    }
	  break;
	}
    }

  if (!match (EOI))
    greska ("Visak simbola na ulazu");
#ifdef ISPIS_POST
  printf ("\n");
#endif

  printf ("Vrednost izraza je %d\n", top (value_stack));

  return 0;
}