1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

duvida: algoritmo recursivo para verificar balanceamento de parentesis numa expressao

Discussão em 'Programação' iniciada por trashCanMan, 7 de Maio de 2007. (Respostas: 16; Visualizações: 2576)

  1. trashCanMan

    trashCanMan Power Member

    boas pessoal!
    ando aqui as voltas com um exercicio para o qual nao consigo chegar a nenhuma solucao :S
    o exercicio consiste em verificar se os parentesis numa expressão matematica estão devidamente balanceados, recursivamente... de notar que ja implementei o metodo de forma iterativa (que costuma ser mais complicado).
    Obrigado pelo vosso tempo!
     
  2. gooden

    gooden Power Member

    receio k n te posso ajudar pk n to a perceber :S
     
  3. hYpe

    hYpe [email protected] Member

    nome_da_funcao(char x, int eskerda, int direita)
    {
    if(char == '\0' && eskerda != direita)
    return false;
    else if(char == '\0' && eskerda == direita)
    return true;
    else if(x == '(')
    eskerda++;
    nome_da_funcao(proximo_caracter, eskerda, direita);
    else if(x == ')'
    direita++;
    nome_da_funcao(proximo_caracter, eskerda,direita);
    else
    nome_da_funcao(proximo_caracter,eskerda,direita);

    }
    ----

    foi feito assim a martelo, mas e' capaz de funcionar.

    pela tua assinatura presumo q estejas a progrmar em java.
    para ires buscar o caracter numero X a uma string fazes nome_da_string.charAt(X);

    boa sorte e depois poe a tua soluçao.
     
  4. gooden

    gooden Power Member

    ok agora k nao ajudo msm nd :P sou incompativel cm java LOOOL
     
  5. inginheiiro

    inginheiiro Power Member

    Código:
    int ContaParent(string msg){
                for (int i=0;i<msg.Length;i++){
                    if (msg[i] == '(')
                    {
                        string nm = msg.Substring(i + 1, msg.Length - (i + 1));
                        return 1+ par(nm);
                    }
                    else
                        if (msg[i] == ')')
                        {
                            string nm = msg.Substring(i + 1, msg.Length - (i + 1));
                            return par(nm)-1;                        
                        }
    
                }
                return 0;
    }
    Se retornar um valor maior que 0, é pq tens esse número de parentisis "(" em excesso.
    Se retornar um valor menor que 0, é pq tens esse número de parentisis ")" em excesso.
    Se retornar 0, é pq está balançeado.

    /ing
     
    Última edição: 7 de Maio de 2007
  6. Rui_Carlos

    Rui_Carlos 1st Folding then Sex

    só por curiosidade, para a string ")1(" que resultado é que as vossas funções devolviam?
    é que matematicamente os parentesis dessa expressão não me parecem estar balanceados... o "contador" dos parentesis nunca pode assumir um valor negativo (pelo menos essa é a minha interpretação do problema, e não testei as vossas funções, mas parece-me que não verificam isso).
     
    Última edição: 7 de Maio de 2007
  7. hYpe

    hYpe [email protected] Member

    pelo menos a mha soluçao dizia que esta certo. e está.. tem o mesmo numero de 'abrir' e 'fechar'.

    agora se a expressao e' valida ou nao, isso ja e' outra conversa...
     
  8. inginheiiro

    inginheiiro Power Member

    a minha função não testa a validade de uma expressão. Não foi isso que percebi do problema proposto. Se for para validar a veracidade da expressão, então tem que se fazer uns ajustes à função.

    /ing
     
  9. Rui_Carlos

    Rui_Carlos 1st Folding then Sex

    eu só referi esse pormenor porque falou-se em expressões matemáticas, mas não sei se isso também era para ser tido em conta.
     
  10. CrazyBomber

    CrazyBomber Power Member

    Também não há-de ser assim tão difícil. Em pseudo-código:

    Código:
    Contador = 0
    Iterar para cada simbolo {
     Se o simbolo for '(': adiciona 1 ao contador
     Se o simbolo for ')' {
      Se o contador for > 0: subtrai 1 ao contador
      Senão: retorna BALANCEAMENTO_INCORRECTO
     }
     Para qualquer outro símbolo: passa à frente [nem sequer é necessário]
    }
    
    Se o Contador == 0: retorna BALANCEAMENTO_CORRECTO
    Senao: retorna BALANCEAMENTO_INCORRECTO
    Acho que é mais ou menos isto, certo? :)
     
  11. trashCanMan

    trashCanMan Power Member

    /**
    *Metodo chamado para verificar balanceamente de parentesis quando o utilizador pressiona o respectivo botao
    *este metodo utiliza um metodo auxiliar para a implementacao recursiva do algoritmo
    [email protected] expressao expressao no formato infix
    */
    void verificarParentesis(String expressao) {

    String parAbrir = "([{";
    String parFechar = ")]}";
    StringTokenizer strtknzr = new StringTokenizer(expressao, parAbrir + parFechar,true);

    verificarParentesisRecursivoAux(expressao,"",parAbrir,parFechar,strtknzr);
    }

    /**
    *metodo auxiliar para implementacao recursiva do algoritmo de verificacao de balanceamento dos parentesis
    *a string é percorrida recursivamente de forma verificar se um tipo de parentesis é fechado por outro simetrico
    [email protected] expressao expressao no formato infix (note-se que nao vai ser usada, por isso pode ser suprimida)
    [email protected] lidos string que vai guardar os caracteres(parentesis) que foram lidos e esperam confirmacao de "casamento" com simetrico
    [email protected] parAbrir string que guarda os parentesis esquerdos para comparacoes
    [email protected] parFechar string que guarda os parentesis direitos para comparacoes
    [email protected] strtknzr string que guarda os token retirados da expressao, contem somente os parentesis , na ordem original
    */
    void verificarParentesisRecursivoAux(String expressao, String lidos, String parAbrir,String parFechar, StringTokenizer strtknzr){

    if(!strtknzr.hasMoreTokens()){
    txtResultado.setText("Nao introduziu parentesis");
    return;
    }

    String tokenComparar = strtknzr.nextToken();

    if(parAbrir.indexOf(tokenComparar) >= 0){ //signfica que o token é um parentesis do parAbrir
    //expressao.substring(1,expressao.length()-1);
    lidos=lidos.concat(tokenComparar);
    verificarParentesisRecursivoAux(expressao,lidos,parAbrir,parFechar,strtknzr);
    }
    else if(parFechar.indexOf(tokenComparar) >= 0){ //significa que o token é um parentesis do parFechar
    if(lidos.compareTo("") == 0){ //se a string lidos estiver vazia
    txtResultado.setText("A expressao contem mais parentesis a FECHAR do que a ABRIR");
    return;
    }else{
    String aux = lidos.substring(lidos.length()-1); //atribuido o ultimo valor da string lido
    lidos = lidos.substring(0,lidos.length()-2); //retira o valor mais a direita da string
    if(parAbrir.indexOf(aux) != parFechar.indexOf(tokenComparar)){ //se o parentesis do parFechar nao casar com o parentesis do parAbrir
    txtResultado.setText("Encontrou "+tokenComparar+" em vez de "+parFechar.charAt(parAbrir.indexOf(lidos.charAt(parAbrir.indexOf(aux)))));
    return;
    }
    verificarParentesisRecursivoAux(expressao,lidos,parAbrir,parFechar,strtknzr); //se for fechar e casar o parAbrir com parFechar volta a comparar
    }

    }
    if(!strtknzr.hasMoreTokens() && lidos.compareTo("") != 0) //se nao houver mais tokens e a string nao estiver vazia
    txtResultado.setText("A expressao contem mais parentesis a ABRIR do que a FECHAR");
    else
    txtResultado.setText("Expressao correcta");
    }

    /*Aqui fica a minha conclusão, ainda com bugs, que devido a carga de trabalhos que tenho, não vou ter oportunidade de resolver, podem estar claros, mas sinceramente, nao consigo olhar mais para este exercicio :zzz: se houver alguem interessado em continuar o meu trabalho, sera bem-vindo.
    boa noite pro pessoal e boas programacoes*/
     
  12. souto

    souto To fold or to FOLD?

    podes usar uma pilha (stack) para resolver isso :)
     
  13. trashCanMan

    trashCanMan Power Member

    pois.. mas o objectivo era mesmo usar um metodo recursivo :007:
     
  14. souto

    souto To fold or to FOLD?

    em q linguagem pretendes implementar isso?
     
  15. MadOnion

    MadOnion Folding Member

    A linguagem acima é JAVA. Estou a ver que as aulas de IPM andam a fritar-te o miolo :-D

    O metodo da pilha é interessante, porque para o balanceamento estar correcto, é preciso que o primeiro parentese a fechar seja igual ao parentese que está no topo na pilha, e assim sucessivamente, ou seja, se for um parentese para abrir, coloca na pilha, se for para tirar, retira da pilha e compara-o com o topo.
    Depois retorna-se o boolean se a pilha está vazia e se está balanceado, mas isto de forma iterativa.
     
  16. souto

    souto To fold or to FOLD?

    Se fosse só IPM... Terrível!

    É possível fazer de forma recursiva (para percorrer a string), penso.
    Pode ser uma saída para o problema inicial.

    Cumprimentos.
     
  17. trashCanMan

    trashCanMan Power Member

    O metodo que postei ja é recursivo!!! tem é bugs que ja nao tenho cabeça para deslindar >( mas a ideia consiste em guardar numa string auxiliar os parentesis lidos para posterior comparacao! basicamente é o mesmo principio que ir metendo para a pilha!!

    Hasta la pasta!
     

Partilhar esta Página