Avaliando uma expressão infixa.

Com as duas ultimas postagens discutindo uma metodologia para o calculo de expressão pós-fixa, amplia-se o senso de continuidade no assunto com o reaproveitamento do material elaborado, tornando o estudo atual em um caso de transformar uma expressão infixa em pós-fixa.

Um ponto importante a ser implementado nesta conversão é a prioridade do operador em uma expressão infixa e como o parêntese altera em qual ordem a operação irá ser executado.

O tratamento da precedência deverá seguir a tabela apresentado anteriormente e incluir parênteses no tratamento, considere uma função prcd(opr1, opr2)  cujo resultado determina a ação a ser tomada, aonde opr1  e opr2 são operadores na expressão, sempre que a precedência de opr1 for maior ou igual que opr2, retorna VERDADE, do contrario sendo menor, retorna FALSO, no exemplo abaixo temos a seguinte situação:

INFIXA	PÓS-FIXA
X + Y * Z	X Y Z * +
( X + Y ) * Z	X Y + Z *

               Em ambos os casos, a ordem dos operando se manteve, uma decisão deve ser feita quando surgir um operador,  guarda-se o mesmo em uma pilha  e continua-se montando a pós-fixa, no próximo operador a ser encontrado, este será comparado com o valor armazenado para definir a precedência da operação, para o controle de armazenamento dos dados será utilizada a pilha, que será esvaziada quando o símbolo de maior precedência for encontrado.

passo símbolo conversão Pilha 1 X X 2 + X + 3 Y X Y + 4 * X Y +, * 5 Z X Y Z +, * 6 X Y Z * + 7 X Y Z * +

               No tratamento de parênteses a regra a ser incluída consiste em armazenar o parêntese esquerdo na pilha até encontrar um parêntese direito, retirar os operadores da pilha até encontrar o parêntese esquerdo armazenado.

passo símbolo conversão pilha 1 ( ( 2 X X ( 3 + X (, + 4 Y X Y (, + 5 ) X Y + 6 * X Y + * 7 Z X Y + Z * 8 X Y + Z * +

Caso o processo de conversão do algoritmo lhe pareça confuso, repare que o método de conversão trabalha de dentro para fora, sempre selecionando o conteúdo dos parênteses primeiro, semelhante maneira que seria dada a resposta em formato manual, ao invés de usar lápis e papel para lembrar a ordem dos operadores, utilizamos a pilha para armazenar o operador de menor prioridade.

Todo o código em linguagem C para avaliar uma expressão infixa utilizando pilhas está incluído na próxima postagem "Rotinas para infixa" que completa o tema sobre analise de expressões.

Rotinas para pós-fixa.

CÓDIGO-FONTE: https://github.com/r-bauer/postfix/archive/master.zip

Utilizando os arquivos da pilha genérica, as rotinas a seguir apresentam a passagem do algoritmo para código em “C” da avaliação feita anteriormente, bastando alterar o tipo de dado que será usado pela analise de expressão no arquivo stackapp. h,  a informação do valor  inserido.

... typedef struct tagDATA {     float     fVal; } SDATA; ...

Novamente o arquivo stackdrv.c é utilizado para a aplicação, a rotina recebe como entrada a expressão que foi passada através da linha de comando, o que torna toda a expressão em caracteres de uma string com dígitos e símbolos, a única novidade em relação ao texto anterior sobre a avaliação de uma expressão fica por conta da conversão do valor de entrada, argc tem o total de argumentos que foi passado e cada elemento de argv aponta para uma string com o operador ou símbolo, usando as funções IsNumber e IsOperator para identificar e decidir qual tratamento, abaixo segue a versão da rotina simplificada para facilitar o entendimento, a rotina completa incluída os comentários e tratamentos de erro estão disponíveis no github.

int StackDriver(int argc, char *argv[]) {     SDATA sdEl;      // dado temporario,     SSTACK *stk;     // a pilha que serah usada     int iCnt;        // para ser usado como contador de loop     float fRes;     stk = appCreateStack(argc);       // cria e inicializa a pilha     for (iCnt = 1; iCnt < argc; ++iCnt)     {         if ( IsNumber(argv[iCnt]) )         {             sdEl.fVal = (float) Atoi(argv[iCnt]);             appPushData(stk, &sdEl);         }         else if ( IsOperator(argv[iCnt][0]) )         {             float fVal1, fVal2;             appPopData(stk, &fVal2);             appPopData(stk, &fVal1);             switch (argv[iCnt][0])             {                 case '+':                         sdEl.fVal = fVal1 + fVal2;                     break;                 case '-':                         sdEl.fVal = fVal1 - fVal2;                     break;                 case '/':                         sdEl.fVal = fVal1 / fVal2;                     break;                 case '*':                         sdEl.fVal = fVal1 * fVal2;                     break;                 case '$':                         sdEl.fVal = Expon(fVal1, (int)fVal2);                     break;             }             // salva o resultado na pilha             appPushData(stk, &sdEl);         }     }     appPopData(stk, &fRes);     return (EXIT_SUCCESS); }

               Para a nossa aplicação foram adicionadas uma série de rotinas para ajudar no suporte da avaliação, apesar de varias delas terem equivalentes na biblioteca padrão do“C”, a opção de incluir serve para ilustrar os passos necessários para a resolução e perceber as limitações que o programa possui, a principal em si é a incapacidade de detectar e corrigir um erro, caso seja digitada uma expressão invalida, que não respeite o espaçamento entre símbolos e dígitos. Outros problemas que podem acontecer como a operação para converter string em um valor numérico suporta apenas números inteiros e a função exponencial não aceita expoente negativo.

LOCAL BOOL IsDigit(char c) {       return (c >= '0' && c <= '9'); } LOCAL BOOL IsNumber(char *pStr) {       while (*pStr) {             if (!IsDigit(*pStr)) {                   return FALSE;             }             pStr++;       }       return TRUE; } LOCAL int Atoi(char *pStr) {       int iRet = 0;       while (*pStr) {             iRet *= 10;             iRet += (*pStr++ & 0xF);       }       return (iRet); } LOCAL BOOL IsOperator(char c) {       char cOp[] = {"+-/*$"};       char *ptr;       ptr = cOp;       while (*ptr) {             if (*ptr++ == c)                   return TRUE;       }       return FALSE; } LOCAL float Expon(float fBas, int iExp) {       float fRes;       fRes = fBas;       while (--iExp)             fRes *= fBas;       return fRes; }