Palindromes

[ir8o8]

Hey all, I am doing a Palindrome code and I need some help on my function called int palindrome_fix_location(string) part.

A file, called ​data​, contains some unknown number of lines that contain 1 or more non-space characters. You are to read them all in, and output each along with whether the line is a palindrome or not, disregarding punctuation, spaces, and capitalization.
You will write the following functions (prototypes given) and ​no others​:
● string process(string);​ returns a string such that it is in lower case and contains no
punctuation or spacing
● bool is_palindrome(string);​ should use a ​recursive ​method to determine if the string is a
palindrome
○ Remember that a recursive solution has both a base case (or cases) and a recursive
case (or cases) and you must decide which to use using some sort of logic.
● int palindrome_fix_location(string); ​should be as described below:
○ This function should return a location where some number of characters could be added to a non-palindrome string to make it a palindrome.
○ There are many ways to do this, for example the string ​aabcaa ​can be made into a palindrome by simply reversing and duplicating the string at position 0 (before the string) or position 6 (after the string), but a more elegant solution would determine that you could just add the character ​c ​at location 2.
○ An optimal solution will determine the minimum number of characters to add to the string. You do not need to find the optimal solution but if you do then you will receive 1 extra credit PD point. Likewise, PD deductions will result if your program always reports that it should simply reverse the entire string (or the entire string minus one character) and put it at the beginning or end.
● string palindrome_addition(string, int);​ given a string and the location where a string should be added to make it a palindrome, this should return the text that needs to be added at that location.

This is what I have so far:


#include <iostream>
#include <fstream>
#include <string>
#include <cctype>

using namespace std;

string process(string);
bool is_palindrome(string);
int palindrome_fix_location(string);
/*
string palindrome_addition(string,int);
*/

int main()
{
ifstream infile("data");

string line;
while(getline(infile,line))
{
cout << "Original line: " << line << endl;
cout << "Processed line: " << process(line) << endl;


}
infile.close();
return 0;
}

string process(string l)
{
for (unsigned int i = 0; i < l.length(); i++)
if (l[i] >= 'A' && l[i] <= 'Z')
l[i] = tolower(l[i]);
else if (ispunct(l[i]) || isspace(l[i]))
l.erase(i--,1);
return l;
}

bool is_palindrome(string sen)
{
string temp = " ";

if (sen.length() == 1 || sen.length() == 0)
return true;
if (sen[0] != sen[sen.length() - 1])
for (unsigned int i = 1; i < sen.length() - 1; i++)
temp += sen[i];

return is_palindrome(temp);

}

int palindrome_fix_location(string sen)
{
int i = sen.length();

for (i = sen.length() - 1; i >= 0; i--)
return i;
}

[punksheep]

Hi ir8o8,
I'm amazed how useless are those exercices ^_^~
I suppose you are learning C++ ?
Then if this is not an exam, you may forget about that exercice. If it's a project that will give you "points", then ok.

If you are learning, the "algorithmic" part of the exercice is of no value at all, it makes the exercice complicated without any real learning advantage.
For example, forget about the "recursive thing", that's useless, that's slow, that is never done and you will never see any of that in a real C++ efficient code.

Do you have to focus on efficiency ?

I will say no because good design is always "making the thing works" then "make it right" that means "correct" and maybe robust. Those are the real issue of coding.

For the algorithmic part, a lot is done by the std::string classes of C++.
For example, testing if a string is a palindrome is really easy.
1) copy the string
2) reverse it and compare both
It's not the most efficient at all but the coding style it uses is the most powerful as you obtain a very readable and simple code. Code that you can then optimize "easily" when needed.
For example :

#include <algorithm>
#include <string>

bool isPalindrome(std::string const& s)
{
	std::string reversed(s);	// a copy... so not fast ok ^_^
	std::reverse(reversed.begin(), reversed.end());	// not fast either :oP~
	return s == reversed;
}
...
{
	if(isPalindrome("abba")) ...
	std::string niceText = "abcdefghijklmnopqrstuvwxyz";
	if(isPalindrome(niceText)) ...
}

The code is far far from being fast but it is so readible ^_^
One fast version would be to parse the string from both side begin() and end() and moving character by character one at a time and compare the character at each step. If they differ, then you'll have the difference and the position of the difference.

Your string functions are too low-level style for me :).
If it's for the exercice, go ahead but the code is kind of ugly and not readable like that.
For example, you can improve your test a bit, if you go this way, by replacing "if c between 'A' and 'Z'" by "if isalpha(c)" for example. I saw you used isspace() etc. already.

I may use something like this myself :

std::string getCanonical(std::string const& initialString)
{
	// I'll make a copy of s here
	std::string cleanedString;
	for(auto const e : initialString)
	{
		cleanedString += getCanonical(e);
	}
}

Then I'll put all the ugly thing in the function getCanonical() for e (a character).

For the readability, you can also split your is_palindrome() function into simple task.
is_palindrome() just testing that.
And you can define an other "is_palindrome" function with high tolerance. That version may produce a "cleaned" copy of the string, reducing your initial string to a "canonical" string that you can test with your simple version of is_palindrome() instead of mixing both functionalities.

To make it even more simple, I would copy the initial string two times :
1) to a "canonical" string for the matter of palindrome comparison : that is "ABba" becomes "abba" for example and "a B ba" becomes "abba" also.
2) to a string version that doesn't change the position of the characters... because this is required for the function that will determine the position of the difference and also the string to "insert" to make the string a palindrome.

Determining what string to add where, is not that easy.
The "brute" force version of that kind of test will end-up being wrong or inefficient and probably a good solution will use dynamic programmation or a specialized text tool like (maybe) an automata.

I hope it can help a bit.

Just for your information, when it comes to "test" the insertion of strings in a string, you can use the insert() function of std::string. That make it more easy to model and your algorithm will be more robust. It maybe a bit slow compare to some other ways to do it but not that slow :).

Sorry, I don't have much code to give you... palindrome are boring to me :) and so useless \o/

Have fun anyway and continue to give feedback on your work ;) if you need a co-pilot's eye check :D