Avaliando uma expressão pós-fixa

Definição básica para infixa, pós-fixa e pré-fixa e como interpretar através do uso de uma pilha na aplicação, para isso considere que a representação mais comum de uma expressão é a infixa, utilizando o operador + e os operando X e Y, temos a soma no formato:

X + Y

               Ainda existem duas outras notações para representar a soma de X e Y com o símbolo +, sendo:

+ X Y      pré-fixa

X Y +      pós-fixa

               Fica simples através desta apresentação que os prefixos “pré”, “pós” e “in” indicam a posição dos operando em relação ao operador. Apesar da dificuldade de se avaliar esse tipo de expressão em um primeiro momento, lembre que + X Y, assemelha-se a analise léxica de uma função como add(X,Y).

               Outro caso que devemos considerar é o da precedência de um operador, aonde iremos sempre interpretar X + Y * Z como X + (Y * Z), ou seja, para reescrever esta expressão para notação pós-fixa , obedece-se as mesma regras de precedência.

X + Y * Z	Converte multiplicação
X + YZ*	Converte adição
XYZ *+	Pós-fixa

               Com o uso de parênteses a precedência tem aguardar a resolução dentro dos mesmos.

(X + Y) * Z	Converte adição
(XY+) * Z	Converte multiplicação
(XY+)Z*	Parentes desnecessários
XY+Z*	Pós-fixa

               Para a linguagem C existem 4 operações binárias nativas, adição subtração, multiplicação e divisão, através do símbolos +, /, * e -. Uma quinta operação de exponenciação que deverá tornar o símbolo $ em operador. A tabela de precedência a seguir deverá ser ignorada apenas quando ocorrer o uso de parênteses, entretanto uma das vantagens da forma pós-fixa é que não existem parênteses para determinar a prioridade da operação uma vez que a ordem dos operadores na expressão determina a verdadeira sequencia de operações.

PRECEDENCIA
1	Exponenciação	$
2	multiplicação/divisão	*, /
3	adição/subtração	+, -

A forma pós-fixa que posiciona operador na precedência desejada e torna desnecessário o uso do parênteses deveria torna a expressão mais simples para se resolver, não fosse o fato de que ao se costumar com o formato infixa, fica-se difícil avaliar, entretanto através de um algoritmo de pilha para avaliar uma expressão pós-fixa, a tarefa será simples, lembre que a cada operador, refere-se a dois operando anteriores, empilhando os operando até encontrar o operador, desempilha e efetua a ação indicada, voltando a empilhar o resultado, uma simulação da expressão 8 3 4 + - 6 4 2 / + * 2 $ 5 + mostrada abaixo exemplifica a solução.

Simb.	Op1	Op2	Resp.	Pilha
8				8
3				8, 3
4				8, 3, 4
+	3	4	7	8, 7
-	8	7	1	1
6	“	“	“	1, 6
4	“	“	“	1, 6, 4
2	“	“	“	1, 6, 4, 2
/	4	2	2	1, 6, 2
+	6	2	8	1, 8
*	1	8	8	8
2	“	“	“	8, 2
$	8	2	64	64
5	“	“	“	64, 5
+	64	5	69	69

               Interessante reparar que neste caso o tamanho usado pela pilha é inferior ao numero total de operando, o máximo teórico de oito operandos nunca é alcançado devido ao fato de que a cada operador tratado é removido o operando.

Todo o código em linguagem C para avaliar uma expressão pós-fixa utilizando pilha está incluído na próxima postagem “Rotinas para pós-fixa”. O tema sobre analise de expressões continua em “Avaliando uma expressão infixa” e sua programação.

Pilha Genérica

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.

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.