quinta-feira, 4 de abril de 2013

Rotinas para infixa

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


O arquivo stackapp.h terá suporte para três pilhas distintas, a primeira pilha utilizada para checagem de parênteses (programa exemplo da pilha genérica), uma segunda pilha usada na conversão de infixa para pós-fixa e a terceira pilha que calcula a expressão pós-fixa (rotinas para pós-fixa), atendendo assim a proposta de reaproveitar o trabalho feito.


typedef struct tagDATA
{
    char    cOpener;
} SDATA;

typedef struct tagDATAPOST
{
    float     fVal;
} SDATAPOST;

typedef struct tagDATAIN
{
    char     cOpr;
} SDATAIN;

               A rotina de conversão de infixa para pós-fixa discutida na postagem anterior segue abaixo. Dentro do laço principal da rotina que irá acessar cada argumento guardado na variável strInfix, montando o resultado na memória alocada em strPostfix, através dos passos:
1.      Sendo operando (numero), a ordem se mantém, devendo ser inserido na string
2.      Sendo operador, caso o símbolo seja:
a.      Fechar parênteses ‘)’, esvazia a pilha até encontrar ‘(
b.      Abrir parênteses ‘(‘, insere na pilha
c.      -+*/$’, verifica qual a precedência entre o topo da pilha e o atual
                                                              i.     topo maior ou igual, insere topo e empilha atual
                                                             ii.     topo menor, empilha atual
3.      Terminado de percorrer os símbolos, esvazia a pilha, inserindo na string.

LOCAL int MakeStrPostfix(char **strInfix, char **strPostfix)
{
    int argc, iCnt;
    char **argv, *ptrP;
    SSTACK *stkIn;
    SDATAIN sdEl, *sdTop;

    *strPostfix = malloc(strlen(*strInfix) + 1);
    ptrP = *strPostfix;
    *ptrP = '\0';

    argc = CreateTableArg(*strInfix, &argv);

    stkIn = inCreateStack(argc);      

    for (iCnt = 0; iCnt < argc; ++iCnt)
    {
        if ( IsNumber(argv[iCnt]) )
        {
            if (*ptrP == '\0')
                sprintf(ptrP, "%s", argv[iCnt]);
            else
                sprintf(ptrP, "%s %s", ptrP, argv[iCnt]);
        }
        else //IsOperator
        {
            sdTop = inViewTopData(stkIn);

            if (sdTop == NULL) //IsEmpty
            {
                inPushData(stkIn, &argv[iCnt][0]);
            }
            else
            {
                if (argv[iCnt][0] == ')')
                {
                    while( inPopData(stkIn, &sdEl) &&
                           sdEl.cOpr != '(')
                    {
                        sprintf(ptrP, "%s %c", ptrP, sdEl.cOpr);
                    }
                }
                else if (argv[iCnt][0] == '(')
                {
                            inPushData(stkIn, &argv[iCnt][0]);
                }
                else if (Prcd(sdTop->cOpr, argv[iCnt][0]))
                {
                    inPopData(stkIn, &sdEl);
                    sprintf(ptrP, "%s %c", ptrP, sdEl.cOpr);
                    inPushData(stkIn, &argv[iCnt][0]);
                }
                else
                {
                    inPushData(stkIn, &argv[iCnt][0]);
                }                 
            }
        }
    }

    while (inPopData(stkIn, &sdEl) && sdEl.cOpr != '(')
    {
        sprintf(ptrP, "%s %c", ptrP, sdEl.cOpr);
    }

    return (EXIT_SUCCESS);
}

A função resultante é simples e pequena, devido a dois processos feitos em separados, com uma verificação de erro garantindo uma entrada valida e o uso de um vetor que permite acessar cada símbolo individualmente.

Alguns dos programas usados como exemplo neste blog, têm feito uso das variáveis argc e argv, quando programa em C é executado dentro de um SO (Sistema Operacional), este pode passar parâmetros ao programa através destas duas variáveis, argc é um inteiro que representa o numero de textos separados por espaços em branco e argv é um vetor de ponteiros de string. Se o usuário digitar INFIXA 1 + 2 * 3, resultaria em:

argv
--->
[0]
--->
I
N
F
I
X
A
\0


[1]
--->
1
\0







[2]
--->
+
\0







[3]
--->
2
\0







[4]
--->
*
\0







[5]
--->
3
\0






O nome do programa executado fica incluído no parâmetro de entrada junto da expressão a ser analisada, como feito no programa que calculava pós-fixa, em que ficava a cargo do usuário digitar corretamente a entrada, garantindo o funcionamento esperado da rotina.

Entretanto até um erro simples de digitação como escrever 1+2*3 sem espaços para separar os elementos irá gerar um comportamento indesejado, para melhorar a robustez do programa foi incluída a rotina VerifyStrInfix, que formata a string inserindo espaço entre os elementos e verifica se a entrada é valida através das seguintes regras:
1.      Apenas será aceito parênteses, dígitos e operadores
2.      operadores '+-/*$' precisam estar entre dígitos
3.      parênteses '()' tem que estar sempre em pares respeitando a posição
4.      digito não pode ser seguido de outro digito, ex.: 12 + 34   56 * 78 / 90
5.      operadores '+-/*$' não podem estar à esquerda de ')'
6.      operadores '+-/*$' não podem estar à direita de '('

1

if (!( IsOperator(argv[iCnt][jCnt]) ||
       IsBracket(argv[iCnt][jCnt]) ||
       IsDigit(argv[iCnt][jCnt]) ))
{
      return (EXIT_FAILURE);
}

2, 4, 5 e 6

if ((*(ptr-1) == '(' && IsOperator(*(ptr+1))) ||
      (IsOperator(*(ptr-1)) && *(ptr+1) == ')') ||
      (IsOperator(*(ptr-1)) && IsOperator(*(ptr+1))) ||
      (IsDigit(*(ptr-1)) && IsDigit(*(ptr+1))))
{
      return (EXIT_FAILURE);
}

3
if (VerifyBrackets(*strInfix))
      return (EXIT_SUCCESS);
else
      return (EXIT_FAILURE);

               Com VerifyStrInfix garantindo a validade e separando cada elemento com um espaço, a rotina MakeStrPostfix precisa apenas analisar cada elemento. Para facilitar o acesso a cada dado se utiliza a rotina CreateTableArg para montar um vetor de ponteiros, apontando individualmente cada informação, emulando a entrada de dados do SO feita com argc e argv, criando uma tabela de ponteiros e apontando para cada elemento na string com a expressão, substituindo os espaços pelo caractere nulo, a chamada da rotina irá gerar o resultado indicado abaixo.


argc = CreateTableArg(*strInfix, &argv);


ENTRADA
SAIDA






‘1’

‘1’
<---
[0]
<---
argv



‘  ‘

‘\0’







‘+’

‘+’
<---
[1]





‘  ‘

‘\0’







‘2’

‘2’
<---
[2]





‘  ‘

‘\0’







‘*’

‘*’
<---
[3]

argc
= 5


‘  ‘

‘\0’







‘3’

‘3’
<---
[4]





‘\0’

‘\0’








               Fechando a avaliação de expressão infixa usamos a função CalcInfix que agrega as demais sub-rotinas, fazendo a validação da entrada, convertendo infixa em pós-fixa, calculando à pós-fixa e apresentando o resultado final.

int CalcInfix(int argc, char *argv[])
{
      char *strInfix, *strPostfix;
      float fRes;
      int i;

      i = VerifyStrInfix(argc, argv, &strInfix);

      if (i == EXIT_SUCCESS)
      {
            MakeStrPostfix(&strInfix, &strPostfix);
            CalcPostfix(&strPostfix, &fRes);
            printf("%f\n", fRes);
      }

      return (i);
}

               Esta versão apresenta uma série de melhorias contendo a verificação de erros e suporte a exponenciação com inteiro negativo, porem continua a falta de suporte a números fracionários na entrada, facilmente contornado, como exemplo substitua a expressão 8 * 0.5 com 8 * (1/2) na entrada.

               Todos os arquivos do projeto podem ser encontrados no github.

Nenhum comentário:

Postar um comentário