Oi pessoal…
Eu estava aqui bolando algum exercício de recursividade em C para minha monitoria. Só consegui pensar em problemas clássicos ou em problemas em que a recursividade não fazia muito sentido, ou em problemas difíceis demais para uma turma de algoritmos. Veio em mente o problema do balanceamento de parênteses em uma expressão. Acho que a recursividade não é muito indicada aqui, mas vamos lá. Se tiverem sugestões, estou aceitando
De qualquer forma, eu queria que vocês analisassem este código pra ver se existe uma solução mais inteligente que esta usando (suspeito que sim :oops: ). Detalhe: tem que usar recursividade!
#include <stdio.h>
#include <stdlib.h>
int verificaExpressao(char *expressao);
int verificaExpressao(char *expressao,int posicao,int contador);
int verificaExpressao(char *expressao)
{
return verificaExpressao(expressao,0,0);
}
int verificaExpressao(char *expressao,int posicao,int contador)
{
printf("%i - %c - %i\n",posicao,expressao[posicao],contador);
int resultado = 0;
if(expressao[posicao]=='[code]
#include <stdio.h>
#include <stdlib.h>
int verificaExpressao(char *expressao);
int verificaExpressao(char *expressao,int posicao,int contador);
int verificaExpressao(char *expressao)
{
return verificaExpressao(expressao,0,0);
}
int verificaExpressao(char *expressao,int posicao,int contador)
{
printf("%i - %c - %i\n",posicao,expressao[posicao],contador);
int resultado = 0;
if(expressao[posicao]=='\0' && contador==0)
{
//Se chegou ao fim da string e o contador estiver zerado, a expressao esta balanceada
resultado = 1;
}
else if(expressao[posicao]=='\0' && contador!=0)
{
//Se chegou ao fim da string e o contador nao estiver zerado, a expressao nao esta balanceada
resultado = 0;
}
else if(contador<0)
{
//Se em algum momento o contador ficar negativo a expressao eh invalida, porque a expressao eh algo como ")4+3("
resultado = 0;
}
else if(expressao[posicao]=='(')
{
//Se encontrar um abre parenteses, chama recursivamente incrementando a posicao e o contador
resultado = verificaExpressao(expressao,posicao+1,contador+1);
}
else if(expressao[posicao]==')')
{
//Se encontrar um fecha parenteses, chama recursivamente incrementando a posicao e decrementando o contador
resultado = verificaExpressao(expressao,posicao+1,contador-1);
}
else
{
//Se encontrar qualquer outro caractere, chama recursivamente incrementando a posicao apenas
resultado = verificaExpressao(expressao,posicao+1,contador);
}
return resultado;
}
int main()
{
char expressao[40] = "( 38*(20+x)/80 )/128+(4/(38+85*(32-x)))";
if(verificaExpressao(expressao))
{
printf("Expressao balanceada\n");
}
else
{
printf("Expressao nao balanceada\n");
}
system("pause>>null");
return 1;
}
[/code]' && contador==0)
{
//Se chegou ao fim da string e o contador estiver zerado, a expressao esta balanceada
resultado = 1;
}
else if(expressao[posicao]=='[code]
#include <stdio.h>
#include <stdlib.h>
int verificaExpressao(char *expressao);
int verificaExpressao(char *expressao,int posicao,int contador);
int verificaExpressao(char *expressao)
{
return verificaExpressao(expressao,0,0);
}
int verificaExpressao(char *expressao,int posicao,int contador)
{
printf("%i - %c - %i\n",posicao,expressao[posicao],contador);
int resultado = 0;
if(expressao[posicao]=='\0' && contador==0)
{
//Se chegou ao fim da string e o contador estiver zerado, a expressao esta balanceada
resultado = 1;
}
else if(expressao[posicao]=='\0' && contador!=0)
{
//Se chegou ao fim da string e o contador nao estiver zerado, a expressao nao esta balanceada
resultado = 0;
}
else if(contador<0)
{
//Se em algum momento o contador ficar negativo a expressao eh invalida, porque a expressao eh algo como ")4+3("
resultado = 0;
}
else if(expressao[posicao]=='(')
{
//Se encontrar um abre parenteses, chama recursivamente incrementando a posicao e o contador
resultado = verificaExpressao(expressao,posicao+1,contador+1);
}
else if(expressao[posicao]==')')
{
//Se encontrar um fecha parenteses, chama recursivamente incrementando a posicao e decrementando o contador
resultado = verificaExpressao(expressao,posicao+1,contador-1);
}
else
{
//Se encontrar qualquer outro caractere, chama recursivamente incrementando a posicao apenas
resultado = verificaExpressao(expressao,posicao+1,contador);
}
return resultado;
}
int main()
{
char expressao[40] = "( 38*(20+x)/80 )/128+(4/(38+85*(32-x)))";
if(verificaExpressao(expressao))
{
printf("Expressao balanceada\n");
}
else
{
printf("Expressao nao balanceada\n");
}
system("pause>>null");
return 1;
}
[/code]' && contador!=0)
{
//Se chegou ao fim da string e o contador nao estiver zerado, a expressao nao esta balanceada
resultado = 0;
}
else if(contador<0)
{
//Se em algum momento o contador ficar negativo a expressao eh invalida, porque a expressao eh algo como ")4+3("
resultado = 0;
}
else if(expressao[posicao]=='(')
{
//Se encontrar um abre parenteses, chama recursivamente incrementando a posicao e o contador
resultado = verificaExpressao(expressao,posicao+1,contador+1);
}
else if(expressao[posicao]==')')
{
//Se encontrar um fecha parenteses, chama recursivamente incrementando a posicao e decrementando o contador
resultado = verificaExpressao(expressao,posicao+1,contador-1);
}
else
{
//Se encontrar qualquer outro caractere, chama recursivamente incrementando a posicao apenas
resultado = verificaExpressao(expressao,posicao+1,contador);
}
return resultado;
}
int main()
{
char expressao[40] = "( 38*(20+x)/80 )/128+(4/(38+85*(32-x)))";
if(verificaExpressao(expressao))
{
printf("Expressao balanceada\n");
}
else
{
printf("Expressao nao balanceada\n");
}
system("pause>>null");
return 1;
}