Exemplo implementado em C de um algoritmo simples para resolver expressões numéricas simples, contendo as operações *, /, + e -. Bom para treinar conceitos de recursão.
Bom... o algoritmo é extremamente simples:
calcular(s):
Procurar o caracter '+' em s. Se achar:
Separar a string antes e depois do '+'.
Chamar calcular() para cada uma delas e somar.
Retornar o valor.
Procurar o caracter '-' em s. Se achar:
Separar a string antes e depois do '-'.
Chamar calcular() para cada uma delas e subtrair.
Retornar o valor.
Procurar o caracter '*' em s. Se achar:
Separar a string antes e depois do '*'.
Chamar calcular() para cada uma delas e multiplicar.
Retornar o valor.
Procurar o caracter '/' em s. Se achar:
Separar a string antes e depois do '/'.
Chamar calcular() para cada uma delas e dividir.
Retornar o valor.
Retornar o valor de s convertido para número.
O funcionamento do algoritmo será o seguinte: a função recursiva calcular() vai quebrar a string na seguinte ordem: primeiro somas, depois subtrações, depois multiplicações, depois divisões, e ir calculando. Por exemplo, se entrarmos com a expressão "1+2*2-3", acontecerá o seguinte:
- A função quebra a string no '+':
- Agora a função será chamada para o primeiro pedaço e para o segundo. No segundo pedaço, ela quebra no '-':
- Agora a função será chamada para o segundo e para o terceiro pedaço. No segundo pedaço, ela quebra no '*':
- Bom, hora das funções retornarem, não? Agora elas vão retornar na ordem inversa à ordem que quebraram a string. Ou seja, efetuaram primeiro a multiplicação:
- Então, a subtração:
- E, finalmente, a soma, que foi quebrada primeiro:
Como você pôde perceber, a idéia é quebrar a string na prioridade inversa à que as operações devem ser realizadas, porque é do argumento com o qual a função é chamada por último que o retorno é obtido primeiro. Vamos à implementação em linguagem C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int calcular(char *s)
{
char *p;
if((p = strchr(s, '+')))
{
*p = 0;
return calcular(s) + calcular(p+1);
}
if((p = strchr(s, '-')))
{
*p = 0;
return calcular(s) - calcular(p+1);
}
if((p = strchr(s, '*')))
{
*p = 0;
return calcular(s) * calcular(p+1);
}
if((p = strchr(s, '/')))
{
*p = 0;
return calcular(s) / calcular(p+1);
}
return atoi(s);
}
int main(int argc, char **argv)
{
printf("%d\n", calcular
(argv
[1]));
return 0;
}
E, é claro, o teste:
paulo@antartica:~ $ gcc expr.c
paulo@antartica:~ $ ./a.out 1+2*2-3
2
paulo@antartica:~ $ ./a.out 2*2+1-3
2
paulo@antartica:~ $ ./a.out 1-3+2*2
2
paulo@antartica:~ $ ./a.out -222+11*2
-200
