Estruturas de Dados 2005/2006
1
Inversão de uma Sequência
Inverter uma sequência de caracteres a partir do stdin:
#include <stdio.h>
#include<stdlib.h>
#include "pilhas.h"
{*** interface para Pilhas ***}
. . .
{*** Inverter uma sequencia de caracteres ***}
void InvSeq()
{ char car;
Pilhadechar Pcar; // Pilha de caracteres
Pcar = criarP(); // cria uma nova Pilha
car = getchar();
while( (car != EOF) && (isalpha(car)) )
{
Pcar = sobrepoe(car, Pcar);
car = getchar();
}
while( !vaziaP(Pcar) )
{
car = topo(Pcar);
putchar(car);
Pcar = retira(Pcar);
}
}
Estruturas de Dados 2005/2006
2
Simulação iterativa de Cálculo Recorrente
“Desrecorrência” do cálculo recorrente: utilização de Pilha para simular as sucessivas
chamadas recorrentes
. . .
Pilhadeint Pint;
// Pilha de inteiros
. . .
// Calculo do valor do factorial de n>=0
Pint = criarP(); // cria uma nova Pilha de inteiros
Pint = sobrepoe(n, Pint);
while( n > 0 )
{
n--;
Pint = sobrepoe(n, Pint);
}
// n = 0, caso de paragem da recorrencia
Pint = retira(Pint);
// tirar o zero
factorial = 1;
while( !vaziaP(Pint) )
{
factorial = factorial * topo(Pint);
Pint = retira(Pint);
}
// factorial == n!
. . .
Estruturas de Dados 2005/2006
3
Concordância de Parêntisis
Dada uma expressão aritmética, verificar se os parêntisis estão equilibrados:
#define TRUE 1
#define FALSE 0
typedef int BOOL;
char
car;
Pilhadechar Pcar;
// Pilha de caracteres
. . .
//Cada ( e’ colocado na pilha; cada ) retira o par da pilha
Pcar = criarP(); // cria uma nova Pilha (vazia) de carateres
continua = TRUE;
while( continua )
{
car = getchar();
// ler o proximo caracter
switch(car)
{ case ’(’ : Pcar = sobrepoe(car, Pcar);
break;
case ’)’ : if(!vaziaP(Pcar)) Pcar = retira(Pcar);
else continua = FALSE; // erro: ( sem par a fechar
break;
case ’\n’: continua = FALSE; // acabou a expressao
Estruturas de Dados 2005/2006
4
fimdelinha = TRUE;
break;
}
//
//
//
//
}
Aqui: { pilha vazia OU fim de linha } ->
{ pilha vazia E fim de linha } OU { pilha vazia E NOT(fim de linha) }
OU { NOT(pilha vazia) E fim de linha }
=> { parentisis equilibrados } OU { parentisis ) a mais } OU { parentisis ( a mais }
if (vaziaP(Pcar) && fimdelinha)
. . .
// expressao correcta
else
. . .
// ERRO: Parentisis desiquilibrados
Estruturas de Dados 2005/2006
5
Verificar se uma palavra é um Palı́ndromo
. . .
Pilhadecar Pcar;
Filadecar Fcar;
// Pilha de caracteres
// Fila de caracteres
. . .
Pcar = criarP(); // cria uma Pilha vazia
Fcar = criarF(); // cria uma Fila vazia
while( !fimdelinha(stdin) )
{
car = getch(input);
Pcar = sobrepoe(car, Pcar);
Fcar = juntar(car, Fcar);
}
capicua = TRUE;
factorial = 1;
while( (!vaziaP(Pcar)) && (!vaziaF(Fcar)) && capicua )
{
if( topo(Pcar) == frente(Fcar) )
{
Pcar = retirar(Pcar);
Fcar = remover(Fcar);
} else capicua = FALSE;
}
. . .