/* 
  Este programa gera todas as expressoes bem formadas de parenteses com um dado
  numero de pares de parenteses.  Este programa guarda as expressoes geradas na
  memoria, de forma que nao recomendo tentar gerar expressoes com muitos
  pares... 
*/

#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;
}

/* libere(): destroi a lista apontada por p */

void libere(Celula *p)
{
  Celula *q;

  while (p) {
    q=p->prox;
    free(p);
    p=q;
  }
}

/*
  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)
{
  if (n==1) {
    Celula *p, *q;

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

    p=q->prox=(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 q;
  } else {
    Celula *esq, *dir, *tot_inicio, *tot_fim, *parte_inicio, *parte_fim;
    long k, m_esq;

    tot_inicio=tot_fim=(Celula *)malloc(sizeof(Celula));
    /* tot vai ser uma lista com cabeca de lista */
    if (tot_fim==NULL) {
      printf("Faltou memoria...!\n");
      exit(-3);
    }
    tot_fim->prox=NULL;

    n--;
    for (k=0; 2*k+1<n; k++) {
      m_esq=2*k+1;
      esq=lista_exprs(m_esq);
      dir=lista_exprs(n-m_esq);
      parte_inicio=prod(esq, dir, &parte_fim);
      libere(esq);
      libere(dir);

      tot_fim->prox=parte_inicio->prox; 
      tot_fim=parte_fim;
      free(parte_inicio);
      /* jogamos fora a cabeca de lista da lista parte */

    }
    return tot_inicio;
  }
}

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;

  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;  
}