Balanceamento de parênteses - solução mais inteligente que esta

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;
}

' && contador==0) { //Se chegou ao fim da string e o contador estiver zerado, a expressao esta balanceada resultado = 1; } else if(expressao[posicao]=='

#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;
}

' && 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]

4 Respostas

Topicos relacionados