ESTRUTURA DE DADOS - PILHAS

[Guest Wandey]

AE GALERA!!!

tenho Q RESOLVER UM PROBLEMINHA NA FACULDADE E ESTOW COM MUITA DIFICULDADE NA DISCIPLNA ESTRUTURA DE DADOS.... SE TIVER ALGUÉM Q POSSA ME AJUDAR.... SEREI MUITO GRATO....

QUESTÃO: ESCREVA UM ALGORITMO (EM C OU PORTUGOL) QUE USA UMA PILHA PARA VERIFICAR SE UMA DADA CADEIA DE CARACTERES É OU não PALÍNDROMO. POR EXEMPLO: "SUBINOONIBUS" É PALÍNDROMO, POIS PODE SER LIDA DA ESQUERDA PARA DIREITA E DA DIREITA PARA ESQUERDA.

AJUDA AE GNT!!!!

[Durub]

Faça uma função que verifica se é palindromo. Tem dois jeitos (tem mais com certeza, mas só consigo pensar em dois agora) de resolver isso.

1º - Escreva toda a string em um novo char inversamente, depois verifique com strcmp da string.h se são iguais.

2º - Verifique diretamente. Por exemplo:

if(primeiro_caractere != ultimo_caractere)
    return NAO_E_PALINDROMO;

Pelo que eu me lembre (não tenho muito conhecimento nessa área) tudo que é alocado dentro de uma função vai para o stack. (me corrijam se eu estiver errado)

Abraços.

[Guest Kassi]

É estranho fazer certas coisas com pilha, mas no seu caso você poderia fazer o seguinte:

Na hora que estiver empilhando guarde os caracteres num vetor, depois desempinhe guardando em outro vetor, assim se o primeiro vetor for igual ao segundo a sequencia de caracteres é um palindromo.

Verifique se você pode usar essa tática para resolver o problema com o seu professor.

Do jeito q o Durub falou, de verificar o primeiro caracter com o ultimo não daria 100% certo, pois estes caracteres podem ser iguais, mas no meio da string ocorrer algo diferente sabe, Ex.:

SALPARASALADAS, o primeiro e ultimo caracteres são iguais, mas a palavra não é um palindromo.

Espero ter ajudado =)

[Durub]

Não foi bem isso que eu quis dizer, foi mais para ilustrar.

Fazer os testes continuamente.

char string[] = "subinoonibus";
int i = strlen(string);
int j = 0;

if(string[j] != string[i])
    return NAO_E_PALINDROMO;
i--;
j++;
if(string[j] != string[i])
    return NAO_E_PALINDROMO;
i--;
j++;
...........

Claro que isto tudo em um do {} while , for, while, tanto faz.

Consegui fazer aqui uma função pelo primeiro método, testei e deu certo.

Abraços.

Editado Julho 2, 2008 por Durub

[Guest Kassi]

Durub, mas temos que lembrar que ele deve usar a estrutura de pilha para resolver a questão. No caso ele deveria guardar a string na hora de empilhar e a string formada na hora do desempilhamento, ai sim ele faz a comparação entre as duas. Assim evita comparar caracter por caracter.

=)

[Durub]

Na verdade, não entendo direito como funciona o stack (pilha). Achei (e acho) que tudo que fosse alocado em uma função ia pro stack. (Não que o segundo método se encaixe nisso)

No primeiro método seria utilizado o stack?

Estou precisando mexer um pouco com o assembly. :P

Abraços.

EDIT nos dois posts: Estava escrevendo 'metódo' em vez de 'método'.

Editado Julho 2, 2008 por Durub

[Guest Kassi]

Uma pilha funciona da seguinte maneira: o último elemento empilhado será o primeiro a se desempilhado, e quando desempilho um elemento da pilha não terei mais acesso a ele. Com isso dizemos que não temos como ter um histórico dos elementos de uma pilha sem usar uma segunda estrutura para armazenar os elementos desempilhados.

Na questão devesse analisar a string na hora da entrada (empilhamento) e na hora da saida (desempilhamento), e sempre usando uma estrutura auxiliar (vetor de caracter) para armazenar os dados.

A estrutura de pilha não é útil em todos os casos, assim como todas as outras, então basta o programador analisar o problema a ser resolvido e as estruturas que disponhe para realizar a melhor implementação para o problema em questão.

=)