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 :slight_smile:

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

Gosto de coisas úteis. Que tal você criar um exercício para listar recursivamente os arquivos de um diretório?

Acho que essa cai entre as “coisas difícieis demais” para uma turma de algoritmos e programação C…Eles vão despender boa parte do esforço tentando entender as complicações do C para fazer isso…Mas se ocorrer outra idéia, fique à vontade.

E o que achou da solução acima? Dá pra fazer melhor?

Se eles quiserem moleza, que sentem no pudim como diriam um professor meu. Acho que deverias passar o problema do thingol e até alguns mais complicados. Os que você achar realmente complicados, deixe com desafio. Só não subestime seus alunos, isso não faz bem para ambos: pra você pois será mal visto pelos alunos mais dedicados da sala e para eles, pois poderiam sair dali com conhecimento um pouco mais sólido, desde que estejam com vontade para isso.

Não é esta a questão…As dificuldades que encontrarão não serão algoritmicas. Obter a hierarquia de pastas é uma instância do problema de construção e navegação em árvores. Veja bem, acho o problema interessante, sem dúvidas. Mas penso que eles podem desenfatizar a importância do algoritmo, focando-se nos problemas da linguagem. Já se eu abstraísse o problema focando-me em navegação e construção de árvores, eles ainda não tem noção de estruturas de dados. Mas até vejo isso como menos problemático, porque neste ponto o desafio é predominantemente algoritmico. Eu poderia apresentar o conceito.