Reverse string and Palindrome

Question

input : "A man, a plan, a canal: Panama"

Why does output capital char become small not capital?

output :

x: amanaPlanacanalpanam

y: AmanaplanacanalPanama

#include <iostream>
#include <stdbool.h>
#include <stdio.h>
#include<string.h>
using namespace std;

int isPalindrome(char* x) {
    int i, j = 0;
    char y[50];
    int n = strlen(x);
    for (i = 0; i < n; i++)
        if ((x[i] >= 'a' && x[i] <= 'z') || (x[i] >= 'A' && x[i] <= 'Z'))
            y[j++] = x[i];
    y[j] = '\0';
    n = strlen(y);
    int c = n - 1;
    for (i = 0; i < n - 1; i++) {
        x[i] = y[c];
        c--;
    }
    x[i] = '\0';

when i print x and y :

cout << "x: " << x << "\ny: " << y;

why char are small

output : x: amanaPlanacanalpanam y: AmanaplanacanalPanama

    if (strcmp(x, y) == 0)
        return 1;
    return 0;
}

int main() {
    char x[50];
    cout << "Enter : ";
    scanf_s("%[^\n]", x, sizeof(x));

    if (isPalindrome(x))
        printf("\n true\n");
    else
        printf("\nfalse\n"); 

}

screen for output : output screen

Answer 1

Your code is not really C++. It's C with cin and cout mixed in. C++ lets you do this in a much nicer way! You don't need stdbool header in C++, by the way.

First, let's see how it could be done in C++98, using built-in algorithms. Try it on online!: https://godbolt.org/z/j5s4r91s1

// C++98, v1
#include <algorithm>
#include <cassert>
#include <cctype>
#include <string>

// We adapt the C-compatible signatures to C++
char my_tolower(char c) { return std::tolower(c); }

// We pass the string by const reference, thus avoiding the copy.
// Passing by value would look like is_palindrome(const std::string str)
// and would be wasteful, since that copy is not needed at all.
bool is_palindrome(const std::string &input)
{
    std::string filtered;

    // For each character of the input string (within the {begin(), end()} range),
    // insert at the back of the filtered string only if isalpha returns true
    // for that character. This removes non-letters - space and punctuation.
    for (std::string::const_iterator it = input.begin(); it != input.end(); ++it)
        if (std::isalpha(*it))
            filtered.push_back(*it);

    if (input == "A man, a plan, a canal: Panama")
        assert (filtered == "AmanaplanacanalPanama");

    // Transform the filtered string to lower case: for each character
    // in the {begin(), end()} range, apply the my_tolower function to it, and
    // write the result back to the same range {begin(), ...} 
    std::transform (filtered.begin(), filtered.end(), filtered.begin(), my_tolower);
    if (input == "A man, a plan, a canal: Panama")
        assert (filtered == "amanaplanacanalpanama");

    // Is the string in forward direction {begin(), end()}
    // equal to the string in backward direction {rbegin(), ...}?
    return std::equal (filtered.begin(), filtered.end(), filtered.rbegin());
}

int main()
{
    // For testing, input can be provided directly in the code.
    const char input[] = "A man, a plan, a canal: Panama";

    // We now can plainly state that `input` contains a palindrome.
    assert (is_palindrome(input));
}

Note how assert is used as a crude form of automated testing: we don't have to be entering inputs manually before we get the code working. Up till then, an assertion will suffice. Assertions are a means of conveying to both humans and machines that some condition is true. If the condition is not satisfied, the program terminates, usually with an error message.

Instead of the for loop, we should have used copy_if, but that's only available in C++11 and later:

std::copy_if (input.begin(), input.end(), std::back_inserter(filtered), my_isalpha);

But one shouldn't use the algorithms blindly. In our particular case, they don't improve performance nor make the code more generic. We can simplify things dramatically by explicitly iterating over the input string.

https://godbolt.org/z/s8YYMK3a4

// C++98, v2
#include <algorithm>
#include <cassert>
#include <cctype>
#include <string>

std::string filter_for_palindrome_check(const std::string &input)
{
    std::string result;
    for (std::string::const_iterator it = input.begin(); it != input.end(); ++it)
        if (std::isalpha(*it))
            result.push_back(std::tolower(*it));
    return result;
}

bool is_palindrome(const std::string &input)
{
    const std::string filtered = filter_for_palindrome_check(input);
    return std::equal (filtered.begin(), filtered.end(), filtered.rbegin());
}

int main()
{
    const char input[] = "A man, a plan, a canal: Panama";
    assert (filter_for_palindrome_check(input) == "amanaplanacanalpanama");
    assert (is_palindrome(input));
}

In C++11, we could have used the range-for.

https://godbolt.org/z/WGaezj3oq

// C++11, v1
#include <algorithm>
#include <cassert>
#include <cctype>
#include <string>

std::string filter_for_palindrome_check(const std::string &input)
{
    std::string result;
    for (char c : input)
        if (std::isalpha(c))
            result.push_back(std::tolower(c));
    return result;
}

bool is_palindrome(const std::string &input)
{
    const std::string filtered = filter_for_palindrome_check(input);
    return std::equal (filtered.begin(), filtered.end(), filtered.rbegin());
}

int main()
{
    const char input[] = "A man, a plan, a canal: Panama";
    assert (filter_for_palindrome_check(input) == "amanaplanacanalpanama");
    assert (is_palindrome(input));
}

Now we can begin to experiment with C++20. Note how the algorithm becomes less verbose even after this initial transformation. The pipe syntax is reminiscent of Unix.

https://godbolt.org/z/cM4ova8a5

// C++20, v1
#include <algorithm>
#include <cassert>
#include <cctype>
#include <ranges>
#include <string>
#include <string_view>

// Saves us from typing std:: every time we use these namespaces.
namespace views = std::ranges::views;

// We adapt the C-compatible signatures to C++
bool my_isalpha(char c) { return std::isalpha(c); }
char my_tolower(char c) { return std::tolower(c); }

// It's more general to use a string_view - always passed by value!
// - in place of const string &.
bool is_palindrome(std::string_view input)
{
    // C++17 lets us do it all in a single `using` statement :)
    using views::filter, views::transform, views::reverse;
    std::string filtered;

    std::ranges::copy(input | filter(my_isalpha) | transform(my_tolower), 
        std::back_inserter(filtered));

    return std::ranges::equal(filtered, filtered | reverse);
}

int main()
{
    const char input[] = "A man, a plan, a canal: Panama";
    assert (is_palindrome(input));
}

The C++ standard that's coming after C++20 will likely make it easier to convert a range to a concrete value. In the meantime, Eric Niebler's range-v3 library does the trick.

https://godbolt.org/z/ojo9zWPr9

// C++20, v2 (using Eric Niebler's range-v3)
#include <algorithm>
#include <cassert>
#include <cctype>
#include <ranges>
#include <range/v3/to_container.hpp>
#include <string>
#include <string_view>

namespace views = std::ranges::views;

bool my_isalpha(char c) { return std::isalpha(c); }
char my_tolower(char c) { return std::tolower(c); }

bool is_palindrome(std::string_view input)
{
    using views::filter, views::transform, views::reverse, ranges::to;

    auto const filtered = input 
        | filter(my_isalpha) | transform(my_tolower) | to<std::string>();

    return std::ranges::equal(filtered, filtered | reverse);
}

int main()
{
    const char input[] = "A man, a plan, a canal: Panama";
    assert (is_palindrome(input));
}

Note how the C++ code is now approximating a plain-language description of the algorithm: take the input, only alphanumeric part of it, in lower case, put it into a string. Call the input a palindrome if the string is equal to its reverse.

As you may have guessed, the type of filtered is const std::string.

You can of course ask: why not avoid the intermediate string? Say:

bool is_palindrome(std::string_view input)
{
    using views::filter, views::transform, views::reverse;

    auto const filtered = input | filter(my_isalpha) | transform(my_tolower);

    return std::ranges::equal(filtered, filtered | reverse);
}

This won't compile until we make filtered non-const. That's a bit curious: are the compiler and library designers perhaps trying to tell us something? Yes!

Without said const, this approach works, but filtered here is a lazily evaluated range. Lazy evaluation means that the filtered result is computed only as needed. And here, it's needed twice: for the 1st and 2nd argument to std::ranges::equal. So this will, in general, make things worse even if it appears "simpler". Let's not write such things.

Hopefully this gives you some taste for how much C++ is a different language than C. There're some nifty things in C++, but not all of them are in the standard library. There is IMHO at least one somewhat better alternative to C++20 ranges, e.g. ast-al/rangeless. It's like C# LINQ, but in C++ :)

C++20 ranges work "well" when things are trivial, but become hard to use when you're expecting more complex expressions to "just work" - and they don't. So - the above C++20 examples must be read with this in mind. C++20 ranges aren't an answer to the ultimate question for sure.

Answer 2

If you are using C++, you should use std::string instead and that will make your life easier and code much cleaner. So let's first create a function, that returns a string reversed:

std::string reverse( const std::string &s )
{
    return std::string( s.rbegin(), s.rend() );
}

very simple, right? Now we need a function, that removes all non letters from a string, here it is:

std::string removeNonLetters( std::string s )
{
    auto it = std::remove_if( s.begin(), s.end(), []( char c ) { return not std::isalpha( c ); } );
    return std::string( s.begin(), it );
}

It is little bit more complicated, as we use remove-erase idiom from `std::remove_if() but it is a 2 line function. And last task - we need to make our string all lowercase:

std::string lowerCase( std::string s )
{
    std::transform( s.begin(), s.end(), s.begin(), []( char c ) { return std::tolower( c ); } );
    return s;
}

which uses another algo from standard library - std::transform(), here we can test them all live example, results:

amanaP :lanac a ,nalp a ,nam A
AmanaplanacanalPanama
a man, a plan, a canal: panama

Now combining these 3 functions you can easily achieve your task - to check if a string is a palindrome.

Note: if using standard algorithms is too complicated for you or it is too early for your class, you can easily rewrite them using loops. Point is you should write simple functions, test that they do work and then combine them into more complex task.

Answer 3

The piece of code in which you fill x with the contents of y is not correct, since it does not consider the first element of y. If you start at index c = n - 1, but in the for loop you stop at i < n - 1, the last index you get from y is 2, not 1.

If you want to keep the original upper and lower cases, a possible solution would be to update both i and c in the loop conditions, and to assure that all the indices are correctly swapped:

for (i = 0, c = n - 1; i < n; i++, c--) {
  x[i] = y[c];
}