Hello again! In this video, we are going to write a program which checks for palindromes. A palindrome
is an expression which reads the same way backwards as it does forwards. For example, "Madam, I'm Adam",
m-a-d-a-m-i-m-a-d-a-m, so it is the same way, whether you read it forwards or backwards.
Another example: "Able" was I, ere I saw Elba". "ere" is a poetic or archaic word, which means before or until.
So this is a reference to Napoleon.
"A man, a plan, a canal, Panama".
So space characters, punctuation and capitalization are ignored.
We just look at the actual letters.
Our program is going to prompt the user to enter some input, and it will check whether that input
is a palindrome.
So for example, if I enter "Madam..."
Then "Madam, I'm Adam" is a palindrome.
If I enter "Madam I'd Adam",
So this is not the same going both ways.
We have "m-a-d-a-m", but we have, going backwards,
We have "m-a-d-a-d". So we have a mismatch.
The character 'm' and the character 'd' do not match up.
So this is not a palindrome.
And also, the character 'm' does not match the character 'd'. And it prints out the string up to the letter
'd'.
When we write this program, we are only going to use functions from the standard library
header.
We are not going to write any explicit loops.
You may want to pause the video and think about how you do this, or maybe even try to do it yourself.
The first thing we are going to do is to put the user's input into a consistent state. So we are going
to remove all the spaces, punctuation marks, digits and any "weird" characters the use might type.
And we are also going to convert all the characters to the same case.
We are going to make a copy of the input, in case we need the original for anything else, and we only
want to copy characters which are letters of the alphabet.
We can do that by calling copy_if(). We give the original string as the first iterator range.
We
give a new string as the destination. And then we have a lambda function which calls is_alpha(). This will
return true if the character is a letter of the alphabet, otherwise false.
So this will process every character in the string.
If it is a letter of the alphabet, this will return true and it will be copied into the destination.
Otherwise, it will be ignored.
And then we need to convert all the characters to the same case.
It could be upper or lower.
It does not matter.
We can do this by calling transform(). So we pass our new string as the first iterator range, and then
we pass the start of the same string as the destination iterator.
So this is going to overwrite all the characters in the string, and it is going to transform them by
converting them to lowercase.
So this will convert every character in the string to lowercase - all the characters which survived this
filtration process. For the actual work of comparing the strings, we are going to call mismatch().
So you will remember this takes two iterator ranges, and finds the first mismatching character in
each.
We could make another copy of the string and reverse that, but a simpler way is just to use a reverse
iterator.
So this mismatch is going to go forwards through the string, and it is also going to go backwards through
the string, and it is going to compare the two.
So it will compare the first character in the string to the last character, the first plus one character
to the last minus one and so on. The return value will be a pair of iterators, and this will point
to the first mismatched element in each range.
If the mismatch() algorithm gets all the way through without finding any discrepancies, then both these
iterators will be equal to calling end().
And in that case, we know we have a valid palindrome.
If the returned iterators are not equal to calling end(), then the string is not a palindrome. There is a mismatch.
So if we go back to this, the first iterator of the pair will point to this letter 'm', and the second
one will point to this letter 'd'. As those are the ones which caused the mismatch.
And then we want to print out the string, up to the letter 'd'.
So we call copy(), and we population the other string with the iterator range.
So we pass the begin() iterator as the first argument, and the iterator to the letter 'd' as the second
one.
If we just do that, we get a compiler error, because we have a forward iterator and a reverse iterator,
and you cannot combine them.
But there is a way to convert a reverse iterator to a forward iterator, which is by calling the base() member
function.
So p.second dot base, will take this reverse iterator and return the corresponding forward iterator.
And then it compiles.
And this will populate the "out" string with all the characters from the start of the string, up to
the letter 'd'.
Okay, so let's look at our program.
So we start off by asking the user to enter some input, and then we pass it to a function which returns
a normalized version of the string.
So I have written this as a separate function, because it might be useful for other things.
This will take the string.
We have a new string, which we are going to populate with the result.
We have our copy_if() call.
So this will only copy characters into the string, which are letters of the alphabet.
Then we have our transform() call, which will convert everything to lowercase.
And then we return this new string.
So that is our string "pal". That is the normalized string. Then we have our mismatch() call, so we pass
"pal" as the first iterator range.
We have the reverse
iterator range to this string as the second half of the mismatch.
So this is going to compare the first element of the string to the last, and so on.
This will return a pair of iterators.
If these are both equal to calling end(), then we have a valid palindrome.
If they are different, then we do not have a palindrome; there is a mismatch. p.first is going to
be an iterator to the letter 'm' in our example, and p.second is going to be an iterator to our
letter 'd'.
Then we have our copy(), which is going to make a copy of the string, up to the letter 'd'.
And then we print out our results.
So, "please enter your palindrome".
Yep, "Madam I'm Adam" is a palindrome.
"Madam..."
"Madam I'd Adam" is not a palindrome.
So that is the code that I showed you before, in fact.
So it spots there is a mismatch. Going forwards,
we have an 'm' and, going backwards, we have a 'd'. And the string, up to that letter 'd'.
Okay, so that is it for this video.
I will see you next time.
But until then, keep coding!