WEBVTT 00:00.180 --> 00:06.990 Hello again! In this video, we are going to write a program which checks for palindromes. A palindrome 00:06.990 --> 00:13.740 is an expression which reads the same way backwards as it does forwards. For example, "Madam, I'm Adam", 00:13.740 --> 00:19.740 m-a-d-a-m-i-m-a-d-a-m, so it is the same way, whether you read it forwards or backwards. 00:21.270 --> 00:29.100 Another example: "Able" was I, ere I saw Elba". "ere" is a poetic or archaic word, which means before or until. 00:29.640 --> 00:31.590 So this is a reference to Napoleon. 00:32.730 --> 00:34.350 "A man, a plan, a canal, Panama". 00:37.320 --> 00:40.920 So space characters, punctuation and capitalization are ignored. 00:41.550 --> 00:43.050 We just look at the actual letters. 00:44.450 --> 00:49.790 Our program is going to prompt the user to enter some input, and it will check whether that input 00:49.790 --> 00:50.630 is a palindrome. 00:52.940 --> 00:54.650 So for example, if I enter "Madam..." 00:57.870 --> 01:00.120 Then "Madam, I'm Adam" is a palindrome. 01:01.650 --> 01:04.530 If I enter "Madam I'd Adam", 01:05.760 --> 01:07.920 So this is not the same going both ways. 01:07.920 --> 01:11.550 We have "m-a-d-a-m", but we have, going backwards, 01:11.550 --> 01:15.240 We have "m-a-d-a-d". So we have a mismatch. 01:15.810 --> 01:19.020 The character 'm' and the character 'd' do not match up. 01:21.520 --> 01:23.290 So this is not a palindrome. 01:23.740 --> 01:29.230 And also, the character 'm' does not match the character 'd'. And it prints out the string up to the letter 01:29.230 --> 01:29.560 'd'. 01:33.390 --> 01:37.890 When we write this program, we are only going to use functions from the standard library 01:37.890 --> 01:38.160 header. 01:38.580 --> 01:40.560 We are not going to write any explicit loops. 01:41.670 --> 01:47.310 You may want to pause the video and think about how you do this, or maybe even try to do it yourself. 01:50.000 --> 01:55.850 The first thing we are going to do is to put the user's input into a consistent state. So we are going 01:55.850 --> 02:01.400 to remove all the spaces, punctuation marks, digits and any "weird" characters the use might type. 02:01.820 --> 02:04.700 And we are also going to convert all the characters to the same case. 02:06.620 --> 02:12.020 We are going to make a copy of the input, in case we need the original for anything else, and we only 02:12.020 --> 02:14.870 want to copy characters which are letters of the alphabet. 02:15.770 --> 02:21.470 We can do that by calling copy_if(). We give the original string as the first iterator range. 02:22.370 --> 02:22.640 We 02:22.640 --> 02:28.580 give a new string as the destination. And then we have a lambda function which calls is_alpha(). This will 02:28.580 --> 02:33.590 return true if the character is a letter of the alphabet, otherwise false. 02:34.040 --> 02:36.560 So this will process every character in the string. 02:37.280 --> 02:41.510 If it is a letter of the alphabet, this will return true and it will be copied into the destination. 02:41.960 --> 02:43.220 Otherwise, it will be ignored. 02:44.960 --> 02:47.470 And then we need to convert all the characters to the same case. 02:47.480 --> 02:48.690 It could be upper or lower. 02:48.690 --> 02:49.610 It does not matter. 02:50.480 --> 02:56.570 We can do this by calling transform(). So we pass our new string as the first iterator range, and then 02:56.570 --> 03:00.050 we pass the start of the same string as the destination iterator. 03:00.200 --> 03:04.730 So this is going to overwrite all the characters in the string, and it is going to transform them by 03:04.730 --> 03:05.960 converting them to lowercase. 03:07.280 --> 03:11.930 So this will convert every character in the string to lowercase - all the characters which survived this 03:12.470 --> 03:19.040 filtration process. For the actual work of comparing the strings, we are going to call mismatch(). 03:19.340 --> 03:23.900 So you will remember this takes two iterator ranges, and finds the first mismatching character in 03:23.900 --> 03:24.170 each. 03:25.070 --> 03:30.530 We could make another copy of the string and reverse that, but a simpler way is just to use a reverse 03:30.530 --> 03:31.120 iterator. 03:32.330 --> 03:38.390 So this mismatch is going to go forwards through the string, and it is also going to go backwards through 03:38.390 --> 03:40.130 the string, and it is going to compare the two. 03:41.540 --> 03:47.300 So it will compare the first character in the string to the last character, the first plus one character 03:47.330 --> 03:54.890 to the last minus one and so on. The return value will be a pair of iterators, and this will point 03:54.890 --> 03:57.080 to the first mismatched element in each range. 03:58.340 --> 04:03.440 If the mismatch() algorithm gets all the way through without finding any discrepancies, then both these 04:03.500 --> 04:05.540 iterators will be equal to calling end(). 04:05.870 --> 04:08.120 And in that case, we know we have a valid palindrome. 04:10.170 --> 04:17.040 If the returned iterators are not equal to calling end(), then the string is not a palindrome. There is a mismatch. 04:17.790 --> 04:22.920 So if we go back to this, the first iterator of the pair will point to this letter 'm', and the second 04:22.920 --> 04:27.390 one will point to this letter 'd'. As those are the ones which caused the mismatch. 04:30.240 --> 04:34.230 And then we want to print out the string, up to the letter 'd'. 04:35.880 --> 04:40.500 So we call copy(), and we population the other string with the iterator range. 04:40.890 --> 04:45.840 So we pass the begin() iterator as the first argument, and the iterator to the letter 'd' as the second 04:45.840 --> 04:46.080 one. 04:46.860 --> 04:51.570 If we just do that, we get a compiler error, because we have a forward iterator and a reverse iterator, 04:51.810 --> 04:52.800 and you cannot combine them. 04:53.640 --> 04:58.650 But there is a way to convert a reverse iterator to a forward iterator, which is by calling the base() member 04:58.650 --> 04:59.100 function. 04:59.700 --> 05:05.220 So p.second dot base, will take this reverse iterator and return the corresponding forward iterator. 05:05.730 --> 05:06.630 And then it compiles. 05:08.400 --> 05:13.470 And this will populate the "out" string with all the characters from the start of the string, up to 05:13.470 --> 05:14.090 the letter 'd'. 05:14.700 --> 05:16.320 Okay, so let's look at our program. 05:17.130 --> 05:22.050 So we start off by asking the user to enter some input, and then we pass it to a function which returns 05:22.050 --> 05:23.580 a normalized version of the string. 05:24.150 --> 05:28.380 So I have written this as a separate function, because it might be useful for other things. 05:29.580 --> 05:30.660 This will take the string. 05:31.290 --> 05:34.650 We have a new string, which we are going to populate with the result. 05:35.370 --> 05:36.750 We have our copy_if() call. 05:37.230 --> 05:41.610 So this will only copy characters into the string, which are letters of the alphabet. 05:42.090 --> 05:45.690 Then we have our transform() call, which will convert everything to lowercase. 05:46.410 --> 05:47.910 And then we return this new string. 05:49.640 --> 05:56.480 So that is our string "pal". That is the normalized string. Then we have our mismatch() call, so we pass 05:56.480 --> 05:57.980 "pal" as the first iterator range. 05:58.910 --> 05:59.940 We have the reverse 05:59.960 --> 06:04.640 iterator range to this string as the second half of the mismatch. 06:05.600 --> 06:08.780 So this is going to compare the first element of the string to the last, and so on. 06:11.030 --> 06:12.920 This will return a pair of iterators. 06:13.160 --> 06:17.210 If these are both equal to calling end(), then we have a valid palindrome. 06:19.370 --> 06:25.070 If they are different, then we do not have a palindrome; there is a mismatch. p.first is going to 06:25.070 --> 06:30.560 be an iterator to the letter 'm' in our example, and p.second is going to be an iterator to our 06:30.560 --> 06:31.250 letter 'd'. 06:33.440 --> 06:38.150 Then we have our copy(), which is going to make a copy of the string, up to the letter 'd'. 06:38.600 --> 06:39.980 And then we print out our results. 06:42.890 --> 06:44.270 So, "please enter your palindrome". 06:48.880 --> 06:51.040 Yep, "Madam I'm Adam" is a palindrome. 06:53.400 --> 06:53.910 "Madam..." 06:57.570 --> 06:59.160 "Madam I'd Adam" is not a palindrome. 06:59.550 --> 07:01.860 So that is the code that I showed you before, in fact. 07:02.460 --> 07:05.370 So it spots there is a mismatch. Going forwards, 07:05.370 --> 07:10.740 we have an 'm' and, going backwards, we have a 'd'. And the string, up to that letter 'd'. 07:11.430 --> 07:12.960 Okay, so that is it for this video. 07:13.470 --> 07:14.250 I will see you next time. 07:14.250 --> 07:16.380 But until then, keep coding!