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

#define MMAX 100

/* Usaremos cabeca de lista em todas as nossas listas.  */

typedef struct cel_struct {
  char *expr;
  struct cel_struct *prox;
} Celula;  /* as nossas listas terao Celulas como elementos */

void imprima(Celula *p)
{
  long n_expr=0;

  p=p->prox; /* para ignorar a cabeca de lista */

  while (p) {
    printf("%s (expr. no. %ld)\n", p->expr, ++n_expr);
    p=p->prox;
  }
}

/*
 prod(): recebe duas listas de expressoes bem formadas e devolve uma 
 lista com o "produto cartesiano" das listas, i.e., os elementos da 
 lista resultante sao todas as combinacoes possiveis entre os elementos 
 das duas listas de entrada.  Um ponteiro para a cabeca da lista
 resultante 'e devolvido, assim como um ponteiro para o ultimo elemento
 da lista (parametro fim).
*/

Celula *prod(Celula *p, Celula *q, Celula **fim)
{
  Celula *aux, *qq, *s;
  long c_esq, c_dir;

  *fim=s=(Celula *)malloc(sizeof(Celula)); /* cabeca de lista */
  if (*fim==NULL) {
    printf("Faltou memoria...!\n");
    exit(-3);
  }
  (*fim)->prox=NULL;

  for (p=p->prox; p; p=p->prox) {
    /* comecamos com p->prox para ignorar a cabeca de lista */
    for (qq=q->prox; qq; qq=qq->prox) {
      /* comecamos com q->prox para ignorar a cabeca de lista */

      aux=(Celula *)malloc(sizeof(Celula));
      if (aux==NULL) {
        printf("Faltou memoria...!\n");
        exit(-3);
      }
      c_esq=strlen(p->expr);
      c_dir=strlen(qq->expr);
      aux->expr=(char *)malloc(c_esq+c_dir+3);
      if (aux==NULL) {
        printf("Faltou memoria...!\n");
        exit(-3);
      }
      *aux->expr='(';
      strcpy(aux->expr+1, p->expr);
      strcpy(aux->expr+1+c_esq, qq->expr);
      *(aux->expr+1+c_esq+c_dir)=')';
      *(aux->expr+2+c_esq+c_dir)='\0';
      
      aux->prox=NULL;
      (*fim)->prox=aux;
      *fim=aux;
    }
  }
  return s;
}

/* lista(): devolve um ponteiro para uma lista com a unica expressao bem-formada */
/* com 1 par de parenteses.  Esta lista nao tem cabeca de lista. */

Celula *lista_1()
{
  Celula *p;

  p=(Celula *)malloc(sizeof(Celula));
  if (p==NULL) {
    printf("Faltou memoria...!\n");
    exit(-3);
  }

  p->expr=(char *)malloc(3);
  if (p==NULL) {
    printf("Faltou memoria...!\n");
    exit(-3);
  }

  *(p->expr)='(';
  *(p->expr+1)=')';
  *(p->expr+2)='\0';
  p->prox=NULL;

  return p;
}


/*
  lista_exprs(): recebe um inteiro n.  Devolve um ponteiro para a cabeca
  de uma lista que contem todas as expressoes bem formadas de parenteses
  com n pares de parenteses.  Usa a decomposicao vista em sala.  Suponha
  que E[n] denota o conjunto das expressoes bem formadas com n pares de
  parenteses.  Entao
  
    E[n] = { () }                            se n==1
    E[n] = (E[1]E[n-1]) uniao (E[3]E[n-3]) 
                        uniao (E[5]E[n-5])  
                        ...
                        uniao (E[n-1]E[1])   se n > 1.

*/

Celula *lista_exprs(long n)
{
  long l, ll;

  Celula *resp;

  Celula cab[n];  /* vetor de cabecas de listas */ 
                  /* cab[l] vai ser a cabeca de lista da lista que contera */
                  /* as expressoes bem-formadas com 2*l+1 pares de parenteses. */

  Celula *fim_da_lista[n];
                   /* vamos tambem manter um ponteiro apontando para o fim de */
                   /* cada lista encabecada pelos cab[]. */
      
  Celula *esq, *dir, *tot_inicio, *tot_fim, *parte_inicio, *parte_fim;

  cab[0].prox=fim_da_lista[0]=lista_1();

  for (l=1; 2*l+1<=n; l++) {
    long k, m_esq;

    ll=2*l+1;  /* este 'e o numero de pares de parenteses  */

    fim_da_lista[l]=&cab[l];
    fim_da_lista[l]->prox=NULL;

    for (k=0; 2*k+1<ll-1; k++) {
      m_esq=2*k+1;
      esq=&cab[m_esq/2];
      dir=&cab[(ll-1-m_esq)/2];
      parte_inicio=prod(esq, dir, &parte_fim);

      fim_da_lista[l]->prox=parte_inicio->prox; 
      fim_da_lista[l]=parte_fim;
      free(parte_inicio);
      /* jogamos fora a cabeca de lista da lista parte */
    }
  }
  resp=(Celula *)malloc(sizeof(Celula));
  if (resp==NULL) {
    printf("Faltou memoria...!\n");
    exit(-3);
  }

  resp->prox=cab[n/2].prox;
  return resp;
}

main(int argc, char **argv)
{
  long m, silent=0;
  Celula *solucao;
  
  if (argc==1) {
    printf("Uso: %s m [-s]\n", argv[0]);
    return -1;
  }

  if (sscanf(argv[1], "%ld", &m)<1) {
    printf("Uso: %s m [-s]\n", argv[0]);
    return -2;
  }

  if (argc>2) silent=1;

  if (m%2!=1) 
    printf("Numero de expressoes bem formadas 'e 0 (no. par de parenteses!).\n");
  else {
    solucao=lista_exprs(m);
  
    if (silent) {
      long n_expr;
      solucao=solucao->prox;
      for (n_expr=0; solucao; ++n_expr,solucao=solucao->prox) ;
      printf("Numero de expressoes bem formadas 'e %ld.\n", n_expr);
    } else
      imprima(solucao);
  }

  return 0;  
}