/* ****************************************
\item Grupo 1 (Exercícios com pilha) 
********************************************/
/*
  Uma cadeia de $P$ pode ser especificada por $ww^R$, onde $w$ é uma
  seqüência de $a$'s e $b$'s e $w^R$ é o reverso de $w$, ou seja, $w$
  lido de trás para frente.

  \[P=\{\emptyset,aa,bb,aaaa,abba,bbbb,\ldots\}\]
  
  Faça um programa que, dada uma cadeia de caracteres $x$, determina se $x$
  pertence ou não a $P$, ou seja, se $x$ é da forma $ww^R$.
  
  Exemplo: $abaaba\in P$ e $abbabba\notin P$.
*/

#include <sdtio.h>
void main(){
  char ch, ch2;
  int i, cont=0;  // quantidade de elementos da cadeia
  TipoPilha p1,p2;
  inicializaPilha(&p1);
  inicializaPilha(&p2);
  while (leCaracter(&ch)){
    empilha(&p1,ch);
    cont++;
  }
  if (cont%2!=0)
     printf("Nao pertence\n");
  else{
     for(i=0;i<cont/2;i++){
       desempilha(&p1,&ch);
       empilha(&p2,ch);
     }
     while (!pilhaVazia(p1)){
       desempilha(&p1,&ch);
       desempilha(&p2,&ch2);
       if (ch!=ch2){
         printf("Nao pertence\n");
	 exit(0);
       }
     }
     printf("Pertence\n");
  }
}


/* Faça um programa que recebe uma sequência de parenteses,
  colchetes e chaves, e verifica se a sequências está balanceada.

  Exemplo: A sequência $([])\{\}$ está balanceada, a sequência $([)]$ não está.
*/

#include <sdtio.h>
void main(){
  int bal=1; // supoho inicialmente a sequencia balanceada
  char ch, ch2;
  TipoPilha p;
  inicializaPilha(p);
  while (leCaracter(&ch)){
    if ((ch=='(')||(ch=='[')||(ch=='{'))
      empilha(&p,ch);
    else{
      if (pilhaVazia(p))
	bal=false;
      else{
        desempilha(&p,ch2);
	if !((ch=='(')&&(ch2==')')||
	     (ch=='[')&&(ch2==']')||
	     (ch=='{')&&(ch2=='}'))
	   bal=false;
      }
    }
  if (pilhaVazia(p)&&bal)
    printf("Sequencia balanceada\n");
  else
    printf("Sequencia nao balanceada\n");
}


/* *************************************************
\item Grupo 2 (Formas de alocação de pilhas em um vetor)
**************************************************** */

Como você faria para armazenar eficientemente duas pilhas em um vetor
com MAX posições. Escreva em C as funções para a manipulação de uma das
pilhas.  

Ver notas de aula (aula 2) !!


/* ****************************************
\item Grupo 3 (Listas ligadas) 
****************************************** */


/* Dado um apontador para um nó qualquer de uma lista ligada, insira
um novo nó antes deste nó. Você deve utilizar o seguinte protótipo:\\
{\tt void insereAntes(apontNo p, int x);}.*/

void insereAntes(apontNo p, int x){
  apontNo aux;
  extraiNo(&aux);
  aux->prox=p->prox;
  p->prox=aux;       // insere um novo no apos o no p
  aux->info=p->info; // copia a info de p no novo no
  p->info=x;         // guarda a info no no apontado por p
}


/* Dado um apontador para uma lista ligada de inteiros escreva uma
função que elimina a ocorrência de números iguais na lista.
*/
void removeIgual(apontNo p){
  int val;
  apontNo aux, ant; // ant apontara para o anterior a aux
  val = p->info;    // os nos com val, fora o primeiro, devem ser devolvidos
  ant = p;
  aux = p->prox;
  while (aux!=NULL){ // percorre a lista
    if (aux->info==val){ // devolve o no
      ant->prox=aux->prox;
      devolveNo(aux);
      aux=ant->prox;
    }
    else { // passa para o proximo
      ant=aux;
      aux=aux->prox;
    }
  }
}
void removeIguais(apontNo p){
  while (p!=NULL){
    removeIgual(p);
    p=p->prox;
  }
}


/* ****************************************
\item Grupo 4 (Manipulação de listas) 
****************************************** */

/* Dados dois apontadores para listas ligadas, escreva uma função que
una estas listas em uma nova lista ligada. O que muda quando se utilizam
listas circulares? */
// para listas circulares ver notas de aula
typedef struct _no {
           int info;
           struct _no *prox;
        } no, *apontNo;
// une as listas p1 e p2 em p
void une(apontNo p1, apontNo p2, apontNo p){
  apontNo aux;
  if (p1!=NULL){ // a lista p1 nao e' vazia
    aux=p1;
    while(aux->prox!=NULL) // acha o fim da lista 1
      aux=aux->prox;
    aux->prox=p2; // o fim da lista p1 aponta para a lista p2
    p=p1; 
  }
  else {
    p=p2;
  }
}

/* Dada uma lista circular duplamente ligada com cabeça de lista
  verifique eficientemente se a lista é palíndrome (o conteúdo do
  primeiro nó a esquerda do cabeça de lista é igual ao conteúdo do
  primeiro nó a direita, a assim por diante).*/
typedef struct _no {
           int info;
           struct _no *pesq, *pdir;
        } no, *apontNo;
int checaPal(apontNo p){
   apontNo p1,2;
  p1=p->pesq;
  p2=p->pdir;
  while ((p1!=p2)&&(p1->pesq!=p2)){ // nao cheguei ao fim
    if (p1->info!=p2->info)
      return 0; // encontrei alguem diferente
    p1=p1->pesq;
    p2=p2->pdir;
  }
  if (p1->info==p2->info)
    return 1;  // todos eram iguais
  return 0;
}


/* ******************************************
\item Grupo 5 (árvores) 
******************************************* */

/* Conhecendo os conceitos de árvores de busca, diga em que ordem, os
elementos de 0 a 15 devem ser inseridos para gerar uma árvore de altura
mínima. Explique. */

A cada etapa o numero de
elementos em cada lado da arvore deve diferir em no maximo 1. Para isto,
primeiro escolhemos o elemento 7 (ou 8), o mesmo deve ser feito para as
subsequencias de 0 a 6 e de 8 a 15 (0 a 7 e de 9 a 15).
Respeitando-se a ordem em cada subsequencia, a ordem dos elementos e' 
indiferente. Logo um caso possivel e´:

7 3 5 1 4 6 0 2 12 10 14 11 9 8 15 13 

/* Faça uma função que dado um apontador para a raiz de uma árvore
  conta a quantidade de nós folha (sem filhos) da mesma.*/


typedef struct _no {
           int info;
           struct _no *esq, *dir;
        } no, *apontNo;
int contF=0; // variavel global
void contaFolha(apontNo raiz){
  if (raiz!=NULL){
     if ((raiz->esq==NULL)&&(raiz->dir=NULL)) // no folha
	contF++;
     else{
       contaFolha(raiz->esq);
       contaFolha(raiz->dir);
     }
  }
}