CÓDIGO-FONTE: https://github.com/r-bauer/stackGen/archive/master.zip
Após apresentar em textos anteriores o uso de extern em cabeçalhos, o conceito da pilha e a revisão de ponteiros, pode-se focar somente na implementação de uma pilha genérica, ter um grupo de biblioteca de rotinas ajuda o programador a eliminar o tédio de sempre refazer a codificação ao fazer uma nova aplicação.
Após apresentar em textos anteriores o uso de extern em cabeçalhos, o conceito da pilha e a revisão de ponteiros, pode-se focar somente na implementação de uma pilha genérica, ter um grupo de biblioteca de rotinas ajuda o programador a eliminar o tédio de sempre refazer a codificação ao fazer uma nova aplicação.
Abaixo temos a apresentação dos
arquivos stackgen.h e stackgen.c, com o que denominamos como
primitivas, que vem a serem os comandos básicos que irão movimentar os dados na
memória com suas entradas e saídas.
/*
Arquivo: STACKGEN.H
Autor: Roberto Bauer
Observacoes:
Primitivas genericas
para operacoes de pilhas.
*/
#ifndef
__STACKGEN_H__
#define
__STACKGEN_H__
#undef EXTERN
#ifdef
__STACKGEN_C__
#define
EXTERN
#else
#define EXTERN
extern
#endif
typedef struct tagSSTACK
{
void
* pBase; // aponta
para a base da pilha
int iStackSize; // numero de
dados
int iDataSize; // tamanho do
dado
int iMaxStack; // ultimo
posicao possivel do dado
int iTop; //
posicaoh atual
} SSTACK;
EXTERN void ClearStack( SSTACK * );
EXTERN SSTACK * CreateStack( int,
int );
EXTERN BOOL
PopData( SSTACK *, void * );
EXTERN BOOL
PushData( SSTACK *, void * );
EXTERN void * ViewData( SSTACK *, int );
EXTERN BOOL
DestroyStack( SSTACK * );
#endif // #define
__STACKGEN_H__
|
O uso da struct SSTACK permite encapsular
todos os dados pertinentes a pilha, lembrando que iStackSize e iMaxStack
apesar de se caracterizarem como redundantes, permite maior legibilidade.
/* Arquivo:
STACKGEN.C */
#define
__STACKGEN_C__
#include "Main.h"
.
.
.
|
Função
|
ClearStack
|
Propósito
|
Limpar a pilha de todos os dados armazenados
|
Parâmetros
|
SSTACK *pStk - ponteiro p/ a pilha a ser reinicializada
|
Retorno
|
Nenhum
|
Descrição
|
Limpa a pilha, ao direcionar a posição atual de dados para um item
invalido, deixando assim a pilha vazia. Indica -1(abaixo da linha de limite)
na posição atual dos dados.
|
void
ClearStack(SSTACK *pStk)
{
pStk->iTop =
-1;
}
|
Função
|
CreateStack
|
Propósito
|
Criar a pilha para gerenciamento de dados
|
Parâmetros
|
int iStackSize - total de dados que podem ser armazenados.
int iDataSize - tamanho do tipo de dado armazenado.
|
Retorno
|
pStk - ponteiro para a pilha recém-criada.
NULL - falhou, não foi possível criar a pilha.
|
Descrição
|
Aloca a pilha, determina os limites mínimos e Maximo na mesma, e
certifica que está vazia.
|
SSTACK *CreateStack(int
iStackSize, int iDataSize)
{
SSTACK *pStk;
// certifica
que o tamanho eh valido
if
(iStackSize > 0) {
// cria a
estrutura de gerenciamento da pilha
pStk = (SSTACK *) malloc(sizeof(SSTACK));
if (pStk == NULL) {
// verifica se conseguiu alocar
return
(NULL); // do contrario indica o erro
}
// salva as
informacoes de tamanho da pilha
pStk->iStackSize = iStackSize;
pStk->iDataSize
= iDataSize;
// cria a area de dados da pilha
pStk->pBase = malloc(iStackSize * iDataSize);
if (pStk->pBase == NULL) {
// verifica se conseguiu alocar
free(pStk); //
tendo falhado,
// libera o previamente alocado
return
(NULL); // do contrario indica o erro
}
//
determina o minimo e maximo da pilha
pStk->iMaxStack = iStackSize - 1;
// inicia a pilha
ClearStack(pStk);
// retorna o ponteiro
return
(pStk);
}
else {
return
(NULL); // do contrario indica o erro
}
}
|
Função
|
PopData
|
Propósito
|
Desempilhar os dados armazenados
|
Parâmetros
|
SSTACK *pStk - estrutura com as variáveis de controle da pilha
void *pData - aponta para os dados que foram desempilhados
|
Retorno
|
TRUE - retornou dados validos em pData
FALSE - a pilha está vazia
|
Descrição
|
Recupera um dado da pilha. Se a pilha não estiver vazia, copia a informação
e decrementa o topo da pilha.
|
BOOL PopData(SSTACK *pStk, void
*pData)
{
BYTE *pPos;
// se pilha
vazia
if
(pStk->iTop == -1)
return
(FALSE); // retorna erro
// calcula o
endereco da posicaoh do topo da pilha
pPos
= (BYTE *) pStk->pBase;
pPos +=
(pStk->iTop * pStk->iDataSize);
// copia a informacaoh do topo da pilha, para pData
memmove(pData, pPos, pStk->iDataSize);
--pStk->iTop;
return
(TRUE);
}
|
Função
|
PushData
|
Propósito
|
Empilha o dado recebido
|
Parâmetros
|
SSTACK *pStk - estrutura com as variáveis de controle da pilha
void *pData - aponta para o dado vai ser armazenado
|
Retorno
|
TRUE - armazenou os dados na pilha
FALSE - a pilha está cheia
|
Descrição
|
Salva dado na pilha. Se a pilha não estiver cheia, avança o topo da
lista para o próximo ponto e copia a informação do novo dado.
|
BOOL PushData(SSTACK *pStk, void
*pData)
{
BYTE *pPos;
// pilha estah lotada
if (pStk->iTop == pStk->iMaxStack)
return (FALSE); // indica que naoh ha
espaco
// disponivel p/ novos dados
++pStk->iTop;
// calcula o
endereco da posicaoh do topo da pilha
pPos
= (BYTE *) pStk->pBase;
pPos +=
(pStk->iTop * pStk->iDataSize);
memmove(pPos,
pData, pStk->iDataSize);
return
(TRUE);
}
|
Função
|
ViewData
|
Propósito
|
Ver um elemento da pilha
|
Parâmetros
|
SSTACK *pStk - estrutura com as variáveis de controle da pilha.
int iPos - posição desejada
em termos de distancia do topo.
|
Retorno
|
NULL - a pilha está vazia, ou posição do dado invalida.
pPos - aponta para a posição desejada dentro da pilha
|
Descrição
|
Vê um elemento dentro da pilha. É passado um valor que especifica a posição
do endereço na pilha em relação ao topo, 0 é o topo 1 o elemento abaixo do
topo e 2 é o elemento seguinte a este. Se um valor invalido for passado, a função
retorna NULL, do contrario retorna um ponteiro para posição desejada.
|
void
*ViewData(SSTACK *pStk, int iPos)
{
BYTE *pPos;
if (pStk->iTop == -1)
return (NULL);
if ((pStk->iTop - iPos) < 0)
return (NULL);
// calcula o
endereco da posicaoh do topo da pilha
pPos = (BYTE *) pStk->pBase;
pPos += ((pStk->iTop - iPos) * pStk->iDataSize);
return ((void *)(pPos));
}
|
Função
|
DestroyStack
|
Propósito
|
Termina com o uso da pilha no programa
|
Parâmetros
|
SSTACK *pStk - estrutura com as variáveis de controle da pilha
|
Retorno
|
TRUE - desalocado com sucesso a memória usada pela pilha
FALSE - ponteiro de controle de pilha invalido
|
Descrição
|
Desloca todo o espaço da memória reservado para a pilha.
|
BOOL DestroyStack(SSTACK *pStk)
{
if (pStk->pBase != NULL)
{
free(pStk->pBase);
if (pStk != NULL)
{
free(pStk);
return TRUE;
}
}
return FALSE;
}
|
DESENVOLVENDO A APLICAÇÃO
Com as operações básicas, pode-se
programar uma aplicação, que no exemplo a ser apresentado, irá verificar a
correta sintaxe do uso de parênteses, colchetes e chaves de um arquivo texto
com código “C”, nesta fase do programa, iremos criar o dado da aplicação e
molda-lo, deve-se notar ao observar os arquivos stackapp.c e stackapp.h,
que nestes ficou a adaptação dos dados para o uso das primitivas.
//***********************************************************//
// Arquivo: STACKAPP.H //
// Autor: Roberto Bauer //
// Observacoes: //
// Dados especificos
para aplicacoes de pilhas. //
//***********************************************************//
#ifndef
__STACKAPP_H__
#define
__STACKAPP_H__
#undef EXTERN
#ifdef
__STACKAPP_C__
#define
EXTERN
#else
#define EXTERN
extern
#endif
typedef struct tagDATA
{
int
iLineNo;
char
cOpener;
} SDATA;
#define
appCreateStack(x)
CreateStack((x), sizeof(SDATA))
#define
appPopData(x, y) PopData((x), ((void *)(y)))
#define
appPushData(x, y) PushData((x),
((void *)(y)))
EXTERN SDATA * appViewData( SSTACK *, int );
#endif // #define __STACKAPP_H__
|
//***********************************************************//
// Arquivo: STACKAPP.C //
// Autor: Roberto Bauer //
// Observacoes:
//
// Dados especificos
para aplicacoes de pilhas. //
//***********************************************************//
#define
__STACKAPP_C__
#include "Main.h"
SDATA *appViewData( SSTACK *pStk, int
iPos)
{
return ((SDATA *) ViewData(pStk, iPos));
}
|
Tendo feito a adaptação das
rotinas de pilha, para que estas passem a usar o dado configurado para
aplicação, o controlador da aplicação será a conclusão do programa como
mostrado nos arquivos stackdrv.h e stackdrv.c exibidos abaixo.
//***************************************************************//
// Arquivo: STACKDRV.H //
// Autor: Roberto Bauer //
// Observacoes:
//
// Controlador da
aplicacaoh de exemplo de pilhas. //
//***************************************************************//
#ifndef
__STACKDRV_H__
#define
__STACKDRV_H__
#undef EXTERN
#ifdef
__STACKDRV_C__
#define
EXTERN
#else
#define EXTERN
extern
#endif
int
StackDriver(int, char
*[]);
#endif // #define __STACKDRV_H__
|
Simplificando os passos a serem
realizado, temos de ler um arquivo linha a linha, percorre-se cada linha em
busca de um colchete, parênteses ou chaves, encontrando o símbolo de abertura
“{[(“, irá armazenar a informação na pilha junto do numero da linha onde
encontrou, sempre que encontrar um símbolo de fechamento”}])”, retira o dado da
pilha e realiza a comparação para verificar se o par combina.
//**************************************************************//
// Arquivo: STACKDRV.C //
// Autor: Roberto Bauer //
// Observacoes: //
// Controlador da
aplicacaoh de exemplo de pilhas. //
//**************************************************************//
#define
__STACKDRV_C__
#include "Main.h"
int
StackDriver(int argc, char *argv[])
{
FILE *fin; // arquivo
que sera lido
char
cBuf[512]; //
carrega as linhas do arquivo neste buffer
int
iLineCount; //
contagem atual da linha
SDATA *sdEl; // dado
temporario,
SSTACK *stk; // a pilha que
serah usada
char
c; //
caracter a ser examinado
int
i; //
para ser usado como contador de loop
if (argc !=
2)
{
fprintf(stderr, "Uso: Stackgen
nome.ext\n");
return (EXIT_FAILURE);
}
fin =
fopen(argv[1], "rt");
if (fin == NULL)
{
fprintf(stderr,
"Naoh
conseguir encontrar/abrir o arquivo %s\n",
argv[1]);
return
(EXIT_FAILURE);
}
stk = appCreateStack(40); // cria e
inicializa a pilha
if (stk
== NULL)
{
fprintf(stderr, "Memoria Insuficiente\n");
return
(EXIT_FAILURE);
}
// cria o elemento da pilha
sdEl
= (SDATA *) malloc(sizeof(SDATA));
if (sdEl == NULL)
{
fprintf(stderr, "Memoria Insuficiente\n");
return
(EXIT_FAILURE);
}
iLineCount = 0;
while (!feof(fin))
{
// leh uma
linha do programa C
if
(fgets(cBuf, sizeof(cBuf) - 1, fin) == NULL)
break;
++iLineCount;
// procura
e processa colchete, chaves e parenteses
for (i = 0;
cBuf[i] != '\0'; ++i)
{
switch (c = cBuf[i])
{
case '{':
case '[':
case '(':
sdEl->cOpener = c;
sdEl->iLineNo = iLineCount;
if (!appPushData(stk, sdEl))
{
fprintf(stderr, "Acabou espacoh na pilha\n");
return (EXIT_FAILURE);
}
break;
case '}':
case ']':
case ')':
if (!appPopData(stk, sdEl))
{
fprintf(stderr,
"Perdeu %c na linha %d\n",
c, iLineCount);
}
else
{
if (((c == ')')
&& (sdEl->cOpener != '(')) ||
((c == ']') &&
(sdEl->cOpener != '[')) ||
((c == '}') &&
(sdEl->cOpener != '{')))
{
fprintf(stderr,
"%c na linha %d"
" naoh combina com "
"%c na linha %d\n",
c, iLineCount,
sdEl->cOpener, sdEl->iLineNo);
}
}
break;
default:
continue;
}
}
}
// chegou ao
fim do arquivo. Existe algum item sem par ?
if
(appViewData(stk, 0) != NULL)
{
while (appPopData(stk, sdEl) != 0)
{
fprintf(stderr,
"%c
na linha %d naoh combina\n",
sdEl->cOpener,
sdEl->iLineNo);
}
}
fprintf(stderr, "Checagem
de erro completada\n");
fclose(fin);
return (EXIT_SUCCESS);
}
|
A função usa os argumentos argc e argv de entrada da função main()
para fornecer o caminho do arquivo, escrevendo na linha de comando o nome do
executável junto do nome do arquivo, por exemplo, “stackgen exemplo.c”. O
resultado de sua execução é apresentado abaixo.
C:\Algorit\StackGen\debug>stackgen
Strings.c
Checagem de erro completada
C:\Algorit\StackGen\debug>stackgen
erro.txt
] na linha 6 naoh combina com ( na
linha 6
) na linha 6 naoh combina com [ na
linha 6
( na linha 7 naoh combina
Checagem de erro completada
C:\Algorit\StackGen\debug>
|
O projeto está disponível neste github.
Nenhum comentário:
Postar um comentário