Pilhas

Um pilha é uma estrutura de dados que segue a política FILO (First In Last Out), ou equivalentemente em português: os últimos (a entrar) serão os primeiros (a sair).

Em contraste à pilha, temos a fila, cuja política FIFO (First In First Out) nos entrega o elemento que está há mais tempo na fila.

Mais sobre pilhas aqui.

Para exercitar o uso desta estrutura, foi proposto escrever uma aplicação que diz se uma cadeia de caracteres tem os parênteses casados corretamente.
Por exemplo, a sentença "Esta é uma frase (e aqui vai uma (breve) digressão)" é bem formada.

Veja o código:

/**
* MAC 2301 - Laboratório de Programação
*
* Exercício da aula 1
*
* Assunto: Pilha com vetor
* Aplicação: verificação de uma gramática
*
*   Verificar se um dada seqüência de abre e fecha parênteses
*   e de abre e fecha chaves é bem formada. Exemplos:
*     ()(({})){} é bem formada.
*     (){}{) não é bem formada.
*     (((((( não é bem formada.
*
*   Definição de seqüência bem-formada:
*     Uma seqüência vazia é bem formada;
*     (S) e {S}, onde S é uma seqüência bem formada, são bem formadas;
*     R S, onde R e S são seqüências bem formadas, é bem formada;
*     Somente essas são bem formadas.
*
*   Idéia do algoritmo:
*     Se lermos um abre, empilha
*     Se lermos um fecha, verificamos se casa com o topo da pilha. Se não casar,
*     já é mal formada. Se casar, desempilha e continua lendo.
*     Se chegar até o fim com a pilha vazia, é bem formada. Se soubrou coisa,
*     na pilha, não é.
*
**/

#include 
#include 

#define OVERFLOW 1
#define UNDERFLOW 1
#define TUDO_BEM 0
#define MAX 100

/**
* Função para inserção da pilha
* O topo deve ser passado por referência para poder ser alterado
* Valor de devolução: TUDO_BEM ou OVERFLOW
**/
int empilha(char novoElem, char pilha[ ], int *topo, int tamanho)
{
 if(*topo == tamanho-1)
   return OVERFLOW;
 (*topo)++;
 pilha[*topo] = novoElem;
 return TUDO_BEM;
}

/**
* Função para remoção da pilha
* O topo deve ser passado por referência para poder ser alterado
* Valor de devolução: TUDO_BEM ou UNDERFLOW
**/
int desempilha(char pilha[ ], int *topo, char *valorDesempilhado)
{
 if(*topo < 0)
   return UNDERFLOW;
 *valorDesempilhado = pilha[*topo];
 (*topo)--;
 return TUDO_BEM;
}

/**
* Função booleana que devolve zero se a pilha
* tiver alguma coisa e algo diferente de zero c.c.
**/
int pilhaVazia(char pilha[], int topo)
{
 return (topo < 0);
}

/**
* Procedimento que exibe o conteúdo da pilha.
**/
void imprimePilha(char pilha[ ], int topo)
{
 int i;
 printf("\n Conteúdo da pilha: ");
 for(i = 0; i <= topo; i++)
   printf(" %c ", pilha[i]);
 printf("\n\n");
}

/**
* Aqui a pilha foi implementada com um vetor, onde o topo comeca com -1 e
* ele sempre aponta para a posição do elemento que está no topo.
* Note que há várias maneiras de se implementar!! Esta é apenas uma delas.
*
* Em geral, a implementação da pilha, ou seja, todo o código
* acima, fica num arquivo .c separado e cria-se uma interface
* .h para a estrutura ser usada como uma "caixa preta". Com
* isso, a implementação pode ser modificada ou substituída sem
* precisarmos mexer numa linha sequer do programa principal.
*
* Agora, a aplicação...
*
**/

/**
* Função booleana que devolve zero caso o par de
* caracteres do argumento não casem (ex: '(' e '}')
* e algum valor diferente de zero se casarem.
**/
int casa(char primeiro, char segundo)
{
 return (primeiro == '(' && segundo == ')') ||
   (primeiro == '{' && segundo == '}');
}

/**
* Função booleana que devolve algum valor diferente
* de zero caso o parâmetro seja um abre parênteses ou
* um abre chaves e zero caso seja qquer outra coisa
**/
int ehUmAbre(char umCaractere)
{
 return umCaractere == '(' || umCaractere == '{';
}

/**
* Função booleana que devolve algum valor diferente
* de zero caso o parâmetro seja um fecha parênteses ou
* um fecha chaves e zero caso seja qquer outra coisa
**/
int ehUmFecha(char umCaractere)
{
 return umCaractere == ')' || umCaractere == '}';
}

int main()
{
 int topo;
 int i;
 char desempilhado;
 char pilha[MAX];
 char frase[MAX];

 topo = -1;

 /* Lendo, da entrada padrão, a seqüência */
 printf("\n  Digite uma seqüência de parênteses e chaves ");
 printf("\n  ----> ");
 scanf("%s", frase);

 i = 0;
 /**
  * Enquanto não se chega no fim da string...
  * (o caractere '\0' é o caractere nulo que
  *  representa fim de uma string)
  **/
 while(frase[i] != '\0')
 {
   if(ehUmAbre(frase[i]))
     empilha(frase[i], pilha, &topo, MAX);
   else if(ehUmFecha(frase[i]))
   {
     if(pilhaVazia(pilha, topo))
     {
       printf("\n  Seqüência mal formada. Há um %c na ", frase[i]);
       printf("na posição %d fechando sem abrir.\n\n  ", i+1);
       system("PAUSE");
       return 0; /* já podemos encerrar a execução */
     }
     desempilha(pilha, &topo, &desempilhado);
     if(!casa(desempilhado, frase[i]))
     {
       printf("\n  Seqüência mal formada. Primeiro erro na posição");
       printf(" %d: %c não casa com %c\n\n", i+1, desempilhado,
              frase[i]);
       system("PAUSE");
       return 0; /* já podemos encerrar a execução */
     }
   }
   else
   {
     printf("\n  Ignorando caractere %c...", frase[i]);
   }
   i++;
 }
 if(pilhaVazia(pilha, topo))
   printf("\n\n  Seqüência bem formada.\n\n");
 else
 {
   desempilha(pilha, &topo, &desempilhado);
   printf("\n\n  Seqüência mal formada. Faltou fechar com %c.\n\n",
          desempilhado);
 }
 printf("  ");
 system("PAUSE");
 return 0;
}