C algoritmo para verificar palindromos

Jessé P. de Melo · 2 de maio de 2018

Estou fazendo o seguinte exercicio...

Faça um programa que, dada uma string, diga se ela e um palındromo ou nao. Lembrando que um palındromo e uma palavra que tenha a propriedade de poder ser lida tanto da direita para a esquerda como da esquerda para a direita. Exemplo:

ovo

arara

Socorram-me, subi no onibus em Marrocos.

Anotaram a data da maratona

Fiz o programa que segue. porém está dando erro, aceito novos scripts porém tenho que saber o que aconteceu com o meu para não fazer errado novamente.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void main(void){
    char entrada[100];
    char entradaespelhada[100];
    char metade1[50];
    char metade2[50];
    char metade2espelhada[50];
    int tam=0;
    int metade=0;

    printf("Digite uma frase ou palavra para saber se ela e' um palindromo: ");
    scanf("%s",entrada);

    for (int x=0;x<99;x++){  /*Calculo para saber a metade da string entrada*/
        if (entrada[x]!='\0'){ // enquanto não encontrar o final da string soma mais um. -> ONDE DA ERRO !
            tam=x;
        }
    }

    if (tam%2==0){
        metade=tam/2;
    }
    else{
        metade=(tam-1)/2;
    }

    for(int x=tam;x>0;x--){ /*Populando entrada espelhada para metade 2*/
        entradaespelhada[x]=entrada[tam];
    }

    for(int x=0;x<metade;x++){ /*Populando primeira metade*/
        metade1[x]=entrada[x];
    }
    for (int x=0;x<metade;x++){ /*Populando segunda metade*/
        metade2[x]=entradaespelhada[x];
    }
    if (strcmp(metade1,metade2)==0){ /*Comparando se a primeira e a segunda metade sao igual*/
        printf("A entrada digitada e' palindromo");
    }
    else{
        printf("A entrada digitada nao e' palindromo");
    }
    printf("\nEntrada: %s \nEntrada espelhada:%s  \nmetade1: %s \nmetade2:%s \nmetade espelhada:%s \ntamanho:%i \nmetade:%i",entrada,entradaespelhada,metade1,metade2,metade2espelhada,tam,metade);

}

isrnick · 2 de maio de 2018

Essa parte só vai ler 1 palavra, logo seu programa não vai funcionar para frases:

    printf("Digite uma frase ou palavra para saber se ela e' um palindromo: ");
    scanf("%s",entrada);

Use:

scanf("%99[^\n]", entrada);

Para ler a frase inteira com até 99 caracteres não nulos (o 100º caractere deve armazenar o caractere nulo '\0' indicando o fim da string)... Outra alternativa seria usar fgets().

Esse trecho vai contar mais do que deveria:

    for (int x=0;x<99;x++){  /*Calculo para saber a metade da string entrada*/
        if (entrada[x]!='\0'){ // enquanto não encontrar o final da string soma mais um. -> ONDE DA ERRO !
            tam=x;
        }
    }

Quando o programa reserva o espaço da memória onde serão guardados os dados do vetor de char entrada[100], ele não limpa/esvazia o que já está armazenado nesse espaço da memória, ou seja, é provável que já tenha algum lixo deixado por outros programas que usaram esse espaço da memória anteriormente. O scanf, por sua vez, só vai atualizar os caracteres relevantes quando uma string for lida, por exemplo se o usuário digitar "ovo" apenas as 4 primeiras posições do vetor receberão os caracteres da string 'o', 'v', 'o' e '\0', as demais posições do vetor não são modificadas, pois não é necessário, logo as demais posições do vetor ainda terão o lixo qualquer que já estava lá.

Seu programa está contando todos os caracteres não nulos no vetor inteiro, todas as vezes, logo o lixo qualquer que estiver lá no resto do vetor, e que não faz parte da string lida, também será contado.

Uma maneira melhor para obter o tamanho da string seria assim:

int tam;

for(tam=0; entrada[tam]!='\0'; tam++);

Esse if-else é desnecessário pois se tam é impar, tam/2 é igual a (tam-1)/2:

    if (tam%2==0){
        metade=tam/2;
    }
    else{
        metade=(tam-1)/2;
    }

Também estou vendo que a lógica do seu programa está copiando o caractere nulo '\0', no começo da string invertida, então invalida todo o resto dos caracteres copiados.

Note que não precisa inverter apenas a metade da string, pode inverter a string inteira e comparar com a string não invertida. Também precisa ver que precisa remover todos os caracteres que não são letras da string original (como espaços em branco, hífens (-), e pontuação) para lidar com os casos em que frases são digitadas, então a primeira coisa que eu faria no programa após o usuário digitar a string é copiar apenas as letras da string digitada para outro vetor, para eliminar os caracteres irrelevantes.

Jessé P. de Melo · 2 de maio de 2018

Resolvi o exercício. Sofri um pouco por que tinha esquecido que sem o '\0' strings não terminam.

Muito obrigado isrnick !!!

Segue resolução !

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void main(void){
    char entrada[100];
    char entradaespelhada[100];
    char metade1[50];
    char metade2[50];
    int tam=0;
    int tamcalc=0;
    int metade=0;

    printf("Digite uma frase ou palavra para saber se ela e' um palindromo: ");
    scanf("%99[^\n]", entrada);  //le frase de entrada

    for(tam=0; entrada[tam]!='\0'; tam++); //conta o tamanho da string
    tamcalc=tam; // Variavel para calculo da entrada espelhada
    metade=tam/2;// Variavel para calculo das metades

    for(int x=0;x<tam;x++){ //calculo inverter string entrada
        tamcalc--;
        entradaespelhada[x]=entrada[tamcalc];
    }
    entradaespelhada[tam]='\0';// Finaliza a string

    for(int x = 0; x<metade;x++){//Calculo para a primeira metade da string
        metade1[x]=entrada[x];
    }
    metade1[metade]='\0'; //Finaliza string primeira metade

    for(int x=0;x<metade;x++){ // calculos da segunda metade, essa sendo espelhada do final da string entrada
        metade2[x]=entradaespelhada[x];
    }
    metade2[metade]='\0'; //finaliza string metade2

    if(strcmp(metade1,metade2)==0){ // logica para exibir resposta
        printf("E' palindromo");
    }
    else
        printf("nao e' palindromo");

    printf("\nEntrada:%s \nEntrada espelhada:%s  \nprimeira metade:%s \nsegunda metade:%s \ntamanho da string:%i \nmetade da string:%i",entrada,entradaespelhada,metade1,metade2,tam,metade); // impressao de todas as variaveis usadas.

}

isrnick · 2 de maio de 2018

Aqui está minha versão:

#include <stdio.h>
#include <ctype.h>
#include <string.h>

int main()
{
    char entrada[100], normal[100], invertido[100], c;
    int i, tam;
    
    printf(" Palavra ou frase: ");
    scanf("%99[^\n]", entrada);
    
    tam = 0; //Tamanho = numero de letras na frase
    for(i=0; entrada[i] != '\0'; i++){
        c = toupper(entrada[i]); //Converte para maiúsculo (se for letra)
        if(c >= 'A' && c <= 'Z'){ //Se for uma letra
            normal[tam] = c; //Copia a letra para o vetor normal
            tam++; //Incrementa contador de letras = tamanho
        }
    }
    normal[tam] = '\0'; //Coloca caractere nulo para indicar fim da string
    
    //Inverte a frase inteira
    for(i=0; i<tam; i++)
        invertido[tam-i-1] = normal[i];
    invertido[tam] = '\0'; //Coloca caractere nulo para indicar fim da string
    
    printf(" Normal    -> %s\n Invertido -> %s\n", normal, invertido);
    
    if(strcmp(normal, invertido) == 0)
        printf(" E' palindromo!\n");
    else
        printf(" Nao e' palindromo!\n");
    
    return 0;
}

Boko Moko · 3 de maio de 2018

13 horas atrás, Jessé P. de Melo disse:

if (tam%2==0){ metade=tam/2; } else{ metade=(tam-1)/2; }

Isso pode ser substituido por

metade = (tam-(tam%2))/2;

isrnick · 3 de maio de 2018

4 horas atrás, Boko Moko disse:

Isso pode ser substituido por

metade = (tam-(tam%2))/2;

Ou faz como o Jessé fez no segundo programa e substitui por apenas isso:

metade = tam/2;

Que dá no mesmo nesse caso.

Ansi C · 3 de maio de 2018

Ola ...!

Imaginei o mesmo problema, só que proibindo o uso de cópias bem como da biblioteca string, o que acrescentou ++ de dificuldade, e por motivo didático resolvi. Segue abaixo:

/* verifica palindromos */
#include <stdio.h>
#include <stdbool.h>

char caixa_baixa_( char c ){
	if( 'a' <= c && c <= 'z' )
		return c;
	if( 'A' <= c && c <= 'Z' )
		return c - 'A' + 'a';
	return 0;
	}
unsigned str_len_( char string [] ){
	unsigned elem = 0;
	
	while( '\0' != string [elem] ){
		++elem;
		}
	return elem;
	}
bool verificar_( char este_palindromo [] ){
	char xi, xf;
	unsigned  inic = 0,
		fim = str_len_( este_palindromo );
	
	while( inic < fim ){
		xi = caixa_baixa_( este_palindromo [inic] );
		xf = caixa_baixa_( este_palindromo [fim] );
		if( !xi ){
			inic++;
			}else
		if( !xf ){
			fim--;
			}else
		if( xi != xf ){
			return 0;
			}else{
			++inic;
			--fim;
			}
		}
	return inic;
	}
int main( void ){
	int r = verificar_( "Ovo!!?" );
	printf( "%d\n", r );
	return 0;
	}

Optei por não documentar, haja vista que a principal tarefa exige o simples conhecimento de condicionais mais IF statements.

A vantage em não usar cópia é economia de memória, supondo que seja uma situação imaginária, onde ela é bastante limitada. Se o foco da tarefa supostamente fosse uso de declarações IF esssa seria uma possível solução ideal. É possível adicionar mais completa dificuldade se proibir totalmente o uso de vetores. Testes não realizados!

Boko Moko · 4 de maio de 2018

17 horas atrás, isrnick disse:

Ou faz como o Jessé fez no segundo programa e substitui por apenas isso:

metade = tam/2;

Que dá no mesmo nesse caso.

Bem melhor

Simon Viegas · 7 de maio de 2018

Olá.

Peço desculpas antecipadamente, pois vou ser um pouco prolixo. Tentar demonstrar a minha linha de raciocínio.

1#

Eu penso assim: a primeira coisa para se resolver um problema, é entender o problema. Veja, parece óbvio, mas tendemos a nos preocupar logo em ter uma solução... não estou dizendo que é o caso, mas apenas reforçando que o segredo é entender, não em resolver. Foque no problema... não na solução.

Vamos lá:

Em 02/05/2018 às 16:42, Jessé P. de Melo disse:

Faça um programa que, dada uma string, diga se ela e um palındromo ou nao. Lembrando que um palındromo e uma palavra que tenha a propriedade de poder ser lida tanto da direita para a esquerda como da esquerda para a direita. Exemplo:

ovo

arara

Socorram-me, subi no onibus em Marrocos.

Anotaram a data da maratona

Analisando o enunciado, vemos que o tema central é Palíndromo.. sabe o que é palíndromo? eu particularmente tenho uma ideia.. mas, como "é preciso entender o problema", dei uma olhada no na internet. Wikipédia tem um artigo, veja:

Citação

Um palíndromo é uma palavra, frase ou qualquer outra sequência de unidades (como uma cadeia de ADN; Enzima de restrição) que tenha a propriedade de poder ser lida tanto da direita para a esquerda como da esquerda para a direita. Num palíndromo, normalmente são desconsiderados os sinais ortográficos (diacríticos ou de pontuação), assim como o espaços entre palavras [1]

Leia com atenção essa parte em negrito!

Sacou? Palíndromo NÃO É UM ESPELHAMENTO!!!, ou seja, você está procurando a solução de uma outro problema.

obs.: todo "espelhamento" é um palíndromo, mas nem todo palíndromo é um espalhamento.

2#

Após entender o problema, vamos partir para uma solução:

Lá no Wikipédia tem:

Citação

Rômulo Marinho, veterano palindromista brasileiro, propõe classificar os palíndromos em:

Expliciti - trazem sempre uma mensagem direta, clara e inteligível, como "Socorram-me, subi no ônibus em Marrocos” (palíndromo de autoria anônima, provavelmente o mais conhecido em língua portuguesa).

Interpretabiles - têm coerência, mas requerem esforço intelectual do leitor para serem entendidos, como "A Rita, sobre vovô, verbos atira."

Insensati - cuidam apenas de juntar letras ou palavras sem se preocupar com o sentido, como "Olé! Maracujá, caju, caramelo."

Já vemos que existem 3 classificações. Para o seu contexto faz alguma diferença se vai ser uma ou outra? acho que não! As classificações meio que estão baseadas no "entendimento da frase"... não na estrutura...

Creio que seria basicamente o citado no 1#.

Citação

Num palíndromo, normalmente são desconsiderados os sinais ortográficos (diacríticos ou de pontuação), assim como o espaços entre palavras [1]

Ou seja, você precisa coletar apenas as letras, aí depois testa o espalhamento.

3#

Dica de implementação:

Tente partir do mais simples, para o mais complexo... Por exemplo, em vez de "ter o trabalho de coletar só as letras", de uma forma específica... etc, insira um frase apenas da forma simples. ex.:

Em vez de:

Socorram-me, subi no ônibus em Marrocos.

Use:

socorrammesubinoonibusemmarrocos

Pronto.. ai verifique se esse bagulho acima é palíndromo ou não.

Mais pra frente, parte para uma contexto mais complexo... que seria o tratamento das "letras MAIÚSCULAS", os "caracteres especiais", "acentos", "espaços" etc.

***

No aguardo.

adicionado 7 minutos depois

ADENDO:

@Jessé P. de Melo, sobre:

Em 02/05/2018 às 18:51, Jessé P. de Melo disse:

Resolvi o exercício. Sofri um pouco por que tinha esquecido que sem o '\0' strings não terminam.

Testei aqui e não funcionou:

Como já observado... "Socorram-me, subi no ônibus em Marrocos" é palíndromo.

Poisoned00 · 7 de maio de 2018

#include <string.h>
#include <stdio.h>
#define MAX 100

int main(int argc, char **argv)
{
	char string[MAX];
	int len;
	int j;
	int count;
	count=0;
	
	gets(string);
	len=strlen(string);
	
	j=len-1;
	
	for (int i = 0; i < len	; i++)
	{
		if(string[i]==string[j])
		{
			count++;
			j--;
		}
	}
	if(count==len)
	{
		printf(" eh um palindrome!\n");
	}

	return 0;
}

Fiz uma versão reduzida do código só pra abstração do problema...
Alias , agora que percebi , funciona bem com palavras , mas com frases só funciona se colocar sem caracteres especiais kkk mas ta ae minha contribuição !

Simon Viegas · 7 de maio de 2018

25 minutos atrás, Poisoned00 disse:

Fiz uma versão reduzida do código só pra abstração do problema...
Alias , agora que percebi , funciona bem com palavras , mas com frases só funciona se colocar sem caracteres especiais kkk mas ta ae minha contribuição !

você também está só se baseando no espelhamento (palíndromo é mais que isso)... vide minha postagem anterior.

Jessé P. de Melo · 7 de maio de 2018

@Simon Viegas Desculpe pela demora para responder. Estou com um problema serio para administrar meu tempo, possuo bastante tempo livre porém e de "picado".

Enfim, sou grato a sua explanação e ela faz todo o sentido, nos teste que fiz me livrei da acentuação, pontuação e não me lembro relacionado aos espaços.

Resumindo fiz o processo de tratamento do texto manualmente, no entanto como a correção desse exercicio é um processo onde não ira agregar conhecimento e ainda tenho 6 lista de exercícios para fazer nesse caso em especifico vou deixar do jeito que esta.

Mais uma vez gostaria de deixar claro que sou grato.

Att.

r_msc · 26 de fevereiro de 2021

@isrnick Por favor, como consigo rodar o código usando a tabela ascii? Ao invés da função toupper

Lucca Rodrigues · 26 de fevereiro de 2021

@r_msc A diferença entre letras minúsculas e maiúsculas na tabela ascii é 32, que é o resultado da operação 'a' - 'A', ou 'b' - 'B', etc.

Basta identificar se o caractere em questão é uma letra minúscula, ou seja, se está entre 97 ('a') e 122 ('z'), e se estiver, subtrair 'a' - 'A' de seu valor.