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

Pilhas Com Recursvidade

Discussão em 'Programação' iniciada por lilcrazy, 12 de Março de 2007. (Respostas: 11; Visualizações: 1031)

  1. lilcrazy

    lilcrazy Power Member

    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?
     
  2. HecKel

    HecKel The WORM

    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
     
  3. guilherme

    guilherme Power Member

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

    Warrior Power Member

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

    lilcrazy Power Member

    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 ;-)
     
  6. lilcrazy

    lilcrazy Power Member

    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
     
  7. lilcrazy

    lilcrazy Power Member

    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


     
  8. lilcrazy

    lilcrazy Power Member

    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
     
  9. lilcrazy

    lilcrazy Power Member

    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...
     
  10. TuxBoss

    TuxBoss Power Member

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

    legerdemain Power Member

    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();
     
  12. lilcrazy

    lilcrazy Power Member

    obrigado pessoal. já consegui ;-)
     

Partilhar esta Página