duvida: algoritmo recursivo para verificar balanceamento de parentesis numa expressao

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!
 
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.
 
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:
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:
Rui_Carlos disse:
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).
Clicar para expandir...

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...
 
Rui_Carlos disse:
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).
Clicar para expandir...

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
 
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.
 
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? :)
 
/**
*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
*@param 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
*@param expressao expressao no formato infix (note-se que nao vai ser usada, por isso pode ser suprimida)
*@param lidos string que vai guardar os caracteres(parentesis) que foram lidos e esperam confirmacao de "casamento" com simetrico
*@param parAbrir string que guarda os parentesis esquerdos para comparacoes
*@param parFechar string que guarda os parentesis direitos para comparacoes
*@param 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*/
 
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.
 
MadOnion disse:
A linguagem acima é JAVA. Estou a ver que as aulas de IPM andam a fritar-te o miolo :-D
Clicar para expandir...

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

MadOnion disse:
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.
Clicar para expandir...

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

Cumprimentos.
 
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!
 
Inicie sessão ou registe-se para poder participar.
Back
Topo