// REKURSYWNY ZSTEPUJACY ANALIZATOR SKLADNIOWY
//
// Wczytuje ze standardowego wejscia ciag znakow oznaczajacy wyrazenie
// arytmetyczne wg gramatyki
//
//   <wyrazenie>  ::=  <skladnik>
//                  |  <wyrazenie> + <skladnik>
//                  |  <wyrazenie> - <skladnik>
//
//    <skladnik>  ::=  <czynnik>
//                  |  <skladnik> * <czynnik>
//                  |  <skladnik> / <czynnik>
//
//     <czynnik>  ::=  <liczba>
//                  |  ( <wyrazenie> )
//
//      <liczba>  ::=  0  |  1  |  <liczba> 0  |  <liczba> 1
//
// Drukuje na standardowe wyjscie drzewo rozbioru (lub komunikat
// bledu).


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

#define  max_il_synow  3
#define  max_szer_druku  100
#define  max_wys_druku  40

typedef enum { FALSE = 0, TRUE = 1 }  Boolean;

typedef enum {
  wyraz = 0,
  sklad = 1,
  czyn  = 2,
  licz  = 3
}  nieterminal;

typedef struct dr {
  Boolean czyterm;
  char lk;                       // o ile  czyterm = TRUE
  nieterminal ntm;               // o ile  czyterm = FALSE
  int il_syn;                    // o ile  czyterm = FALSE
  struct dr* syn[max_il_synow];  // o ile  czyterm = FALSE
}  drzewo;

//------------------------------------------------------
// POMOCNICZE:

char  leks;


Boolean  nowyleks(char c, char* nleks) {
    // jesli na wejsciu stoi znak  c , to go sczytuje,
    // zapamietuje w  nleks  i oddaje TRUE;
    // jesli tam stoi inny znak, to nic nie wczytuje i oddaje FALSE
  if (leks == c) {
    *nleks = c;
    do { scanf("%c", &leks); }
    while ((leks < '!' || leks > '~') && leks != '\n');
    return TRUE;
  }
  else  return FALSE;
}


Boolean  blad (char s[]) {
    // sygnalizacja bledu:
    // drukuje napis  s  a nastepnie przerywa wykonanie programu
  printf ("\n  BLAD:  %s\n\n", s); exit(1);
  return FALSE;
}

//------------------------------------------------------
// Serce parsera:
// PO JEDNEJ PROCEDURZE REKURSYWNEJ NA KAZDY NIETERMINAL


Boolean  liczba (drzewo* drz);
Boolean  czynnik (drzewo* drz);
Boolean  skladnik (drzewo* drz);
Boolean  wyrazenie (drzewo* drz);


//   <liczba>  ::=  {0 | 1} {0 | 1}*
Boolean  liczba (drzewo* drz) {
  drzewo drz1;  char nleks;
  if (nowyleks('0', &nleks) || nowyleks('1', &nleks)) {
      // Rozpoznalismy '0' lub '1'; trzeba z tego zrobic <liczba>:
    drz->czyterm = FALSE;
    drz->ntm = licz;
    drz->il_syn = 1;
    drz->syn[0] = (drzewo*)malloc(sizeof(drzewo));
    drz->syn[0]->czyterm = TRUE;
    drz->syn[0]->lk = nleks;
      // Idziemy dalej:
    while (nowyleks('0', &nleks) || nowyleks('1', &nleks)) {
        // Rozpoznalismy kolejne '0' lub '1'; trzeba 
        // dolaczyc do juz istniejacej liczby:
      drz1 = *drz;
      drz->czyterm = FALSE;
      drz->ntm = licz;
      drz->il_syn = 2;
      drz->syn[0] = (drzewo*)malloc(sizeof(drzewo));
      *(drz->syn[0]) = drz1;
      drz->syn[1] = (drzewo*)malloc(sizeof(drzewo));
      drz->syn[1]->czyterm = TRUE;
      drz->syn[1]->lk = nleks;
    }
    return  TRUE;
  }
  else   // Nie rozpoznalismy liczby, trzeba sie wycofac:
    return  FALSE;
}


//   <czynnik>  ::=  ( <wyrazenie> )  |  <liczba>
Boolean  czynnik (drzewo* drz) {
  drzewo drz1;  char nleks;
  if (nowyleks('(', &nleks))
    if (wyrazenie(&drz1))
      if (nowyleks(')', &nleks)) {
          // Rozpoznalismy  ( <wyrazenie> ) ;
          // zestawiamy wiec drzewo wynikowe z  drz1 :

// poczatek konstrukcji drzewa:
        drz->czyterm = FALSE;
        drz->ntm = czyn;
        drz->il_syn = 3;

// dolaczenie syna terminalowego -- lewego nawiasu:
        drz->syn[0] = (drzewo*)malloc(sizeof(drzewo));
        drz->syn[0]->czyterm = TRUE;
        drz->syn[0]->lk = '(';

// dolaczenie syna nieterminalowego -- drzewa  drz1 :
        drz->syn[1] = (drzewo*)malloc(sizeof(drzewo));
        *(drz->syn[1]) = drz1;

// dolaczenie syna terminalowego -- prawego nawiasu:
        drz->syn[2] = (drzewo*)malloc(sizeof(drzewo));
        drz->syn[2]->czyterm = TRUE;
        drz->syn[2]->lk = ')';
        return  TRUE;
      }
      else  return blad ("'(' <wyrazenie> ???  -- oczekiwalem ')'");
    else  return blad ("'('  ???  -- oczekiwalem wyrazenia");
  else  // Nie rozpoznalismy wyrazenia w nawiasie, sprobujmy z liczba
    if (liczba(&drz1)) {  // trzeba z niej zrobic <czynnik>:
      drz->czyterm = FALSE;
      drz->ntm = czyn;
      drz->il_syn = 1;
      drz->syn[0] = (drzewo*)malloc(sizeof(drzewo));
      *(drz->syn[0]) = drz1;
      return  TRUE;
    }
    else  return  FALSE;
}


//   <skladnik>  ::=  <czynnik>  { {* | /} <czynnik>}*
Boolean  skladnik (drzewo* drz) {
  drzewo  drz1, drz2;  char nleks;
  if (czynnik (&drz1)) {
      // powyzsze wywolanie albo sygnalizuje blad albo konstruuje
      // drzewo rozbioru  drz  odpowiadajace nieterminalowi <czynnik>
      // trzeba z niego zrobic <skladnik>:
    drz->czyterm = FALSE;
    drz->ntm = sklad;
    drz->il_syn = 1;
    drz->syn[0] = (drzewo*)malloc(sizeof(drzewo));
    *(drz->syn[0]) = drz1;
      // teraz czesc z gwiazdka:
    while (nowyleks('*', &nleks) || nowyleks('/', &nleks)) {
        // mamy kolejny znak dzialania
      if (czynnik (&drz2)) {
          // Rozpoznalismy kolejny czynnik tworzacy drzewo  drz2 ,
          // trzeba go dolaczyc do starego drzewa  *drz :
        drz1 = *drz;
        drz->czyterm = FALSE;
        drz->ntm = sklad;
        drz->il_syn = 3;
        drz->syn[0] = (drzewo*)malloc(sizeof(drzewo));
        *(drz->syn[0]) = drz1;
        drz->syn[1] = (drzewo*)malloc(sizeof(drzewo));
        drz->syn[1]->czyterm = TRUE;
        drz->syn[1]->lk = nleks;
        drz->syn[2] = (drzewo*)malloc(sizeof(drzewo));
        *(drz->syn[2]) = drz2;
      }
      else  // Rozpoznalismy znak operacji a nastepnie niepoprawny czynnik:
        return blad ("<czynnik> '*/' ???  -- oczekiwalem czynnika");
    }
      // Kolejny znak nie jest operatorem; to znaczy, ze <skladnik>
      // sie zakonczyl
    return TRUE;
  }
  else  // pierwszy <czynnik> jest od razu bledny, wiec nie rozpoznano
        // skladnika; z tego bledu nalezy sie wycofac
    return FALSE;
}


//   <wyrazenie>  ::=  <skladnik> { {+ | -} <skladnik>}*
Boolean  wyrazenie (drzewo* drz) {
  drzewo  drz1, drz2;  char nleks;
  if (skladnik (&drz1)) {
      // powyzsze wywolanie albo sygnalizuje blad albo konstruuje
      // drzewo rozbioru  drz  odpowiadajace nieterminalowi <skladnik>
      // trzeba z niego zrobic <wyrazenie>:
    drz->czyterm = FALSE;
    drz->ntm = wyraz;
    drz->il_syn = 1;
    drz->syn[0] = (drzewo*)malloc(sizeof(drzewo));
    *(drz->syn[0]) = drz1;
      // teraz czesc z gwiazdka:
    while (nowyleks('+', &nleks) || nowyleks('-', &nleks)) {
        // mamy kolejny znak dzialania
      if (skladnik (&drz2)) {
          // Rozpoznalismy kolejny skladnik tworzacy drzewo  drz2 ,
          // trzeba go dolaczyc do starego drzewa  *drz :
        drz1 = *drz;
        drz->czyterm = FALSE;
        drz->ntm = wyraz;
        drz->il_syn = 3;
        drz->syn[0] = (drzewo*)malloc(sizeof(drzewo));
        *(drz->syn[0]) = drz1;
        drz->syn[1] = (drzewo*)malloc(sizeof(drzewo));
        drz->syn[1]->czyterm = TRUE;
        drz->syn[1]->lk = nleks;
        drz->syn[2] = (drzewo*)malloc(sizeof(drzewo));
        *(drz->syn[2]) = drz2;
      }
      else  // Rozpoznalismy znak operacji
            // a nastepnie niepoprawny skladnik:
        return blad ("<skladnik> '+-' ???  -- oczekiwalem skladnika");
    }
      // Kolejny znak nie jest operatorem; to znaczy, ze <skladnik>
      // sie zakonczyl
    return TRUE;
  }
  else  // pierwszy <skladnik> jest od razu bledny, wiec nie rozpoznano
        // skladnika; z tego bledu nalezy sie wycofac
    return FALSE;
}
 
//------------------------------------------------------
// Pomocnicze: DRUKOWANIE DRZEWA

char  druk [max_szer_druku][max_wys_druku];


void  dr_drz (drzewo drz, int* szer, int* wys) {
  int  szer_syna[max_il_synow], wys_syna[max_il_synow], i,j;
  if (drz.czyterm) {
    *szer=*szer+3; *wys=1; druk[*szer-1][*wys-1] = drz.lk;
  }
  else {   // Drzewo nieterminalowe:
    *wys = 0;
    for (i=0; i<drz.il_syn; i++) {
      dr_drz (*drz.syn[i], szer, &wys_syna[i]);
      szer_syna[i] = *szer;
      if (*wys < wys_syna[i])  *wys = wys_syna[i];
    }
    switch (drz.ntm) { 
      case wyraz : druk[*szer-1][*wys+1] = 'W'; break;
      case sklad : druk[*szer-1][*wys+1] = 'S'; break;
      case czyn  : druk[*szer-1][*wys+1] = 'C'; break;
      case licz  : druk[*szer-1][*wys+1] = 'L'; break;
    }
    if (drz.il_syn > 0) {
      for (i=0; i<drz.il_syn; i++)
      for (j=wys_syna[i]; j<*wys+1; j++)
        druk[szer_syna[i]-1][j] = '|';
      for (i=szer_syna[0]; i<*szer-1; i++)  druk[i][*wys+1] = '-';
      for (i=0; i<drz.il_syn-1; i++)
	druk[szer_syna[i]-1][*wys+1] = ',';
    }
    *wys = *wys+2;
  }
}


void  drukuj_drzewo (drzewo drz) {
  int szer,wys,i,j;
  for (i=0; i<max_szer_druku; i++)
   for (j=0; j<max_wys_druku; j++)  druk[i][j] = ' ';
  szer=0;  dr_drz (drz, &szer, &wys);
  for (j=wys-1; j>=0; j--) {
    for (i=0; i<szer; i++)  printf("%c",druk[i][j]);
    printf("\n");
  }
  printf("\n");
}

//------------------------------------------------------
// Program glowny:

int main() {
  drzewo drz;  Boolean ok;

    // Wczytanie pierwszego znaku (z pominieciem niewidocznych):
  do { scanf("%c", &leks); }
  while ((leks < '!' || leks > '~') && leks != '\n');

  ok = wyrazenie(&drz);  printf ("\n");
  if (ok && leks == '\n')  drukuj_drzewo (drz);
  else
    if (ok && leks != '\n') {
      drukuj_drzewo (drz);
      printf ("  SMIECI NA KONCU: %c\n\n", leks);
    }
    else  printf ("  WYRAZENIE BLEDNE\n\n");

  return 0;
}