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.
