Pilhas Com Recursvidade

[lilcrazy]

Hey pessoal!

Eu estou com alguns problemas neste exercício, se alguém puder ajudar agradeço

O objectivo é ler blocos de duas palavras, pegar na primeira palavara e gerar todas as combinações possíveis das operações push e pop dessa palavra na pilha. Isto recorrendo ao uso de recursividade...A operação push equivale a "i", a pop a "o".

Ou seja:

palavra: lol

[iiiooo;oooiii;(...)]


Algum empurrãozinho?

 

[HecKel]

Desculpa, mas sinceramente não percebi muito bem o exemplo..., podes dar um exemplo de uma palavra mais complexa e com mais resultados, sff.

abraços, HecKel

 

[guilherme]

Realmente, pelo tópico achei interessante, mas não compreendi o objectivo.

 

[Warrior]

Todas as operações possíveis de push e pop na palavra? Foi esta parte que a mim me fez confusão.

 

[lilcrazy]

Sorry ter demorado a responder.

O objectivo é dar como input blocos de duas palavras cada, por exemplo:

cao
kil
lo
ol

O maximo de caracteres por palavra é de 100. Cada bloco deverá ter as palavras com o mesmo tamanho, ou seja o tamanho de cao=kil=3, tam lo=ol=2...

Teremos de colocar (push) e retirar (pop) letra a letra para/de uma pilha. A acção Push é dada como "i" e pop como "o". Esta parte até já consegui resolver:

public​

​

​

static void geraSequencias(int num, int num_is, int num_os, String sequencia){
if(num==0){
System.out.println(sequencia);
else{
num--;
if(num_is<tamanho_sequencia)
geraSequencias(num, num_is+1, num_os, sequencia+"i");
if(num_os<tamanho_sequencia)
geraSequencias(num, num_is, num_os+1, sequencia+"o");
}​

}

O que está a aqui a suceder é o seguinte (ainda sem as operações de pilha em si!): inicialmente o primeiro caracter da sequencia irá ter o valor "i" ou "o". É chamada, recursivamente a função e a seguir a um "i" poderá aparecer um "i" ou um "o", e a seguir a um "o" poderá aparecer um "i" ou um "o" por aí em diante. Esta sequência é feita até preencher a String da sequencia de "i"´s e "o"´s. Se a palavra tiver 3 caracteres, o tamanho da sequencia será 3*2, uma vez que poderá haver uma sequência, por exemplo: iiiooo ou oooiii, etc...

Agora preciso de enviar a sequencia para um método e dividir em caracteres, quando encontra o caracter "i", irá ser feito um push para a pilha da primeira palavra do input, se for encontrado um "o" é feito um pop, e por aí em diante. Como são várias sequencias, sempre q se acaba de criar uma, esta irá ser enviada para o tal método e no final irá ser posto numa string resultado os caracteres que surgem ao fazer pop da pilha, se for feito so pop pop pop ("o""o""o" respectivamente) e obrigatoriamente "i""i""i", o resultado sará "". Se for ao contrário o resultado sará (sendo a primeira palavra cao), "oac". E compara o resultado à segunda palavra. Quando for igual, guarda a sequencia que originou esse resultado.

Quem puder ajudar, agradeço ;-)

 

[lilcrazy]

E aqui está esse método (resolvido por mim):

//método que devolve true ou false caso a palavra gerada seja igual à segunda​

public​

​

​

static boolean compara(String seq){

Stack<Character> pilha = new Stack<Character);
char caracterSequencia;
String resultado="";
String oper;
int indice=-1;


//Divide a sequência de i´s e o´s em caracteres​

​

for(int index=0;index<((tamanho_sequencia*2)-1);index++){
caracterSequencia=seq.charAt(index);
oper=String.valueOf(caracterSequencia);
System.out.print(oper);


if(oper.equals("i")){
System.out.print(pilha.push(input1.charAt(indice+1)));
indice++;
}
else if(oper.equals("o")){
while(!pilha.empty()){
System.out.println(pilha.pop());
resultado+=pilha.pop();
System.out.println(resultado);
}
} ​

}

​

//compara a String encontrada através das operações de pilha com a segunda palavra do input​

​

if(!resultado.equals(input2))
return false;
else​

​

return true;
}

E claro no método do gereSequencia(...), as primeiras linhas serão:​

if​

​

​

(num==0){
System.out.println(sequencia);
if(compara(sequencia)==true)
System.out.println("Sequências correctas: "+sequencia);​

}

Os System.out.println() são apenas para verificar os valores que o programa vai gerando para ir tirando as minhas dúvidas. Aqui isto empanca e dá StackOverFlow no último pop ou push :S

 

[lilcrazy]

Um exemplo de input seria:

a
b

(neste caso a nunca vai ser igual a b, por isso nao há nenhuma sequencia possivel para este caso)

O output:

[
io
iaoi​

o]

Até aqui tudo bem (+/-).

As strings "[" e "]" delimitam as varias sequências, vamo-nos focar no interior...

A primeira sequencia possível é: "io" (push, pop)

O que acontece de seguida: primeiro caracter encontrado -> i -> faz push do primeiro caracter da primeira palavra -> a

A PARTIR DAQUI NAO FAZ
segundo caracter encontrado -> o -> faz pop da pilha -> elemento que está no topo -> a

String resultado = "a";

Segunda sequencia: "oi"

O que acontece de seguida: primeiro caracter encontrado -> o -> faz pop da pilha (como nao encontra nada a string fica vazia ainda...ele apenas mostra o "o" que consta como ultimo elemento deste output.

A PARTIR DAQUI NAO FAZ
segundo caracter encontrado -> i -> faz push para a pilha -> elemento que está no topo -> a

a string fresultado fica vazia na mesma

 

[lilcrazy]

passar de string para uma tabela de char

Boas pessoal, ainda relativamente ao exercício de pilhas com recursividade...

o meu método de geração de sequências é o seguinte:

public static void geraSequencias(int tam, int num_is, int num_os, String sequencia){
if(tam==(tamanho_sequencia*2)){
System.out.println(sequencia);
/*if(compara(sequencia)==true)
System.out.println("Sequências correctas: "+sequencia);*/
}
else{
tam++;
if(num_is<tamanho_sequencia)
geraSequencias(tam, num_is+1, num_os, sequencia+"i");
if(num_os<tamanho_sequencia)
geraSequencias(tam, num_is, num_os+1, sequencia+"o");
}
}


Eu queria utilizar uma tabela de char[] em vez da String sequencia como parâmetro deste método. Elaborei este código:

public static void geraSequencias(int tam, int num_is, int num_os, char sequencia[]){
if(tam==(tamanho_sequencia*2)){
System.out.println(sequencia);
/*if(compara(sequencia)==true)
System.out.println("Sequências correctas: "+sequencia);*/
}
else{
tam++;
if(num_is<tamanho_sequencia)
sequencia[tam]='i';
geraSequencias(tam, num_is+1, num_os, sequencia);
if(num_os<tamanho_sequencia)
sequencia[tam]='o';
geraSequencias(tam, num_is, num_os+1, sequencia);
}
}


Quando chamo o método dou como parâmetros os valores: gereSequencias(-1, num_is_maximo, num_os_maximo, sequency);

O valor 0 corresponde ao index inicial da tabela de char, que vai sendo incrementada até ao tamanho_maximo que ela poderá ter. Começa em 0, uma vez que depois será inicialmente incrementada no método...
num_is_maximo e num_os_maximo corresponde, respectivamente, ao número de i´s e número de o´s que a sequencia pode suportar.
sequency é a tabela de char -> char sequency[]=new char[tamanho_maximo];


Aqui o problema é que me dá StackOverFlow.

Input:
a
a

OutPut:
[
ijava.lang.ArrayIndexOutOfBoundsException: 2 (...)

Supostamente, o resultado deveria corresponder ao mesmo que usando Strings (que está bem!):

Input:
a
a

Output:
[
io
oi
]

Alguma ajuda please!

Obrigado

 

[lilcrazy]

Correcção:

O erro não é StackOverFlow mas sim ArrayIndexOutOfBoundsException, pois ele passa o tamanho do array...

E o valor que passo como parâmetro de entrada inicial do método não é 0, mas sim -1, pois ele quando incrementado passa a 0 na primeira iteração, e 0 corresponde a char[0]...primeiro indice...

 

[TuxBoss]

Se aparentemente estás a usar Java, não precisas de char[], tens as operações todas necessárias na Classe String (charAt(), etc).

 

[legerdemain]

e se precisares mesmo de passar a String para um char[], podes usar o método toCharArray()

e.g.

String s = "fsdifjsacd";
char[] c = s.toCharArray();

 

[lilcrazy]

obrigado pessoal. já consegui ;-)