5
\$\begingroup\$

I'm a newbie programmer and was given a task to find if the input word is a palindrome or not. Now, I've written the program to the best of my ability but would like to know how it could be improved.

Also, enlighten me if there are any errors in my program or any other way to make my program more efficient and easy to read!

#include<iostream>
using namespace std;
int main(){
    int a;
    cin>>a; 
    char word[a]; 
    cin>>word;
    bool palindrome= false;
    for(int i=0;i<a;i++) 
    { 
        if(word[i]==word[a-i-1])
            {
                palindrome=true;
            }
            else
            {
                break;
            }
    }
    
    if(palindrome)
    {
        cout<<"palindrome";
    }
    else
    {
        cout<<"not a palindrome";
    }

}
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Besides the checking loop being obviously wrong (step through it in your head!), just what is the length of the string? You are inputting a and using that to size the array, but the string you read can be shorter than that. \$\endgroup\$
    – JDługosz
    Dec 9 '21 at 15:44
  • 1
    \$\begingroup\$ Subtle issue: a char array needs to store one more character than it "contains" for the null character '\0' If the string is "abcd", then your array needs to be five characters long. \$\endgroup\$ Dec 10 '21 at 2:54
  • 3
    \$\begingroup\$ Please don't edit your code after posting to "improve it". This has the effect of invalidating answers that have already been provided. Instead, after taking in the advice gained from the provided answers, you can consider posting a new question with your improved code. \$\endgroup\$
    – theosza
    Dec 10 '21 at 7:54
  • 1
    \$\begingroup\$ Why do you start checking the string at character 1 instead of 0? \$\endgroup\$
    – 9769953
    Dec 10 '21 at 11:21
  • 2
    \$\begingroup\$ Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. \$\endgroup\$
    – pacmaninbw
    Dec 10 '21 at 19:00
17
\$\begingroup\$

Here are some observations that may help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Use more whitespace to enhance readability of the code

Instead of crowding things together like this:

if(word[i]==word[a-i-1])

most people find it more easily readable if you use more space:

    if (word[i] == word[a - i - 1]) 

Fix the bug

ISO C++ forbids the use of a variable length array, which is what you're attempting to create here:

char word[a]; 

It might work in your compiler, but it's not standard. Instead, I'd recommend using std::string. This also allows you to improve the user interface, as per the next suggestion.

Think of the user

Computers are rather good at counting, so why don't we let the computer count the letters instead of relying on the human to do so? I'd suggest changing the interface to only ask for a string from the user and then having the computer count, if that's necessary.

Decompose your program into functions

All of the logic here is in main in one chunk of code. It would be better to create a separate is_palindrome() function to separate that from the input and output.

Carefully consider your algorithm

The algorithm is not wrong in your program, but I think I'd write it a bit differently.

Algorithmic efficiency First, we don't really need to check the entire length of the string, since we're checking the beginning and the ending, we really only need to check half.

Simplicity/Coherence A clearer way to write this would avoid the use of confusing and error-prone control flow (for with break nested in an if else clause). If this is put inside a function, as suggested above, you could write this:

for (size_t i{0}; i < a; ++i ) {
    if (word[i] != word[a - i - 1]) {
        return false;
    }
}      
return true;

Start with an obviously correct version

It's good to start with an obviously correct version, in my view, rather than seeking to optimize from the start. In this case, we could use some standard library functions to mimic the way we'd describe a palindrome in English: "it is a word that is the same forwards as backwards."

bool is_palindrome(const std::string& word) {
    auto revword{word};
    std::reverse(revword.begin(),revword.end());
    return word == revword;
}

This is not as efficient because it allocates and de-allocates a copy of the input word, but it's very obviously correct, which has a lot of advantages when trying to troubleshoot or re-use a function. Not least, if you ultimately decide you need to write a faster version, you can use the obviously correct version to verify that the faster version is also correct.

\$\endgroup\$
4
  • \$\begingroup\$ actually, despite using the strings, i wanted to do this task with help of char arr since i'm learning the basics of c++ right now. \$\endgroup\$
    – Manya Garg
    Dec 9 '21 at 14:19
  • 21
    \$\begingroup\$ @ManyaGarg: I'd argue using std::string is the basics of C++, while char* is getting into advanced, low-level details. \$\endgroup\$ Dec 9 '21 at 21:36
  • \$\begingroup\$ @ManyaGarg: Note that char word[a]; with a non-constexpr a is an ISO C99 feature, and C also lacks any std::string equivalent. Your design would make a lot more sense if this was a C program, although it's still bad program design to require the user to give you an accurate count of the next string input. It creates a trivial buffer overflow where bad input can crash the program if you don't also use the array length as an input length limit, and that bad UI is not worth the tiny optimization of knowing how much to allocate ahead of the read. \$\endgroup\$ Dec 10 '21 at 6:28
  • 6
    \$\begingroup\$ I really want to emphasize that using dynamically-allocated containers is not just a stylistic choice. The code as written will let input longer than the program was told to expect overflow the buffer. Not only is it easier for a beginner to use std::string, but buffer overruns like that are the cause of many, many, many security bugs. So you cannot get into the habit of avoiding them too soon. \$\endgroup\$
    – Davislor
    Dec 10 '21 at 7:37
9
\$\begingroup\$

I'm a newbie programmer and was given a task to find if the input word is a palindrome or not.

I hope that means that you're taking lessons, and this is an assignment. I think you're at a disadvantage in this being your first programming language, so you're having to learn the language and "programming" at the same time.

separate out the tasks

Separate out the code for

  • input
  • output
  • the real work

In this case, the input is a distraction since you have issues reading the input from the user. But if you start with automated test cases, you don't have to worry about that and can come back to it later.

The "real work" would be a function of the form:

bool is_palindrome (std::string_view)

It is given the string to check, so writing the logic doesn't have to worry about reading user input or anything like that. It returns the result as a boolean, and it is not that function's concern what becomes of that result.

Now you can write tests using a library like Catch2, or just write a bunch of calls and check their answers. You can even combine Edward's idea of comparing your result against the "obviously correct but inefficient" version, in a different function.

const char* tests[] = { "abcdcba", "abccba", "George", "tomato" };
for (auto s : tests) {
   const bool check = Stupid_slow_check(s);
   const bool result = is_palindrome(s);
   const bool pass = check==result;
   cout << s << ' ' << check << " Pass=" << pass << '\n';
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ " I think you're at a disadvantage in this being your first programming language, so you're having to learn the language and "programming" at the same time." I don't understand this sentence. What other way is there? Learning programming without a programming language? Learning a programming language without programming in it? \$\endgroup\$
    – Stef
    Dec 10 '21 at 10:28
  • 7
    \$\begingroup\$ @Stef learning another programming language, already knowing how to logically formulate an algorithm for a problem etc. from experience in other languages. Learning C++, already knowing how to program in general, means just concentrating on learning the C++ language. Learning C++ the language and such details of just how can you use for loops, conditional branching, variables, etc. to solve some stated problem, at the same time, is more difficult. \$\endgroup\$
    – JDługosz
    Dec 10 '21 at 14:53
  • \$\begingroup\$ @JDługosz I would have to argue that C++ is one of the best languages to start learning, as it introduces the user to some low-level details that one might not find easy at first, but it will make one a better programmer and make it easier to jump to another language. I find that I don't even have to learn a language like Java or C# just because by learning C++, I can already understand 70 - 80% of the language. If I had started with those languages, I would have been scratching my head at what a pointer is and why my data structures are getting deep copied. \$\endgroup\$ Dec 10 '21 at 16:42
  • \$\begingroup\$ @CaptainHatteras That's an interesting observation. BTW, I learned C++ before Java and C# existed. My first real procedural programming language was UCSD Pascal. But I learned programming on 8-bit BASIC first. \$\endgroup\$
    – JDługosz
    Dec 13 '21 at 15:08
7
\$\begingroup\$

Your implementation is obviously wrong. As soon as there are two letters at equidistance from either end that are the same then your algorithm will output that it's a palindrome. You can test that with input length 4 and word abca for example.

You need to turn the test around and assume palindrome = true until you find a letter pair that doesn't match.

\$\endgroup\$
0
6
\$\begingroup\$

Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

Use the Container Classes in the Standard Template Library (STL)

The code is currently using old C style character arrays, C++ has container classes for arrays of strings, these classes are std::string and std::string_view. If you are going to program in C++ it is better to use the container classes provided. The loop to determine if the word is a palindrome can be only one or two lines of code using the container classes in C++. See the answers to this question.

Possible Logic Issue

It would be better to assume the word is a palindrome until the test fails rather than assuming the word is not a palindrome. This would allow the code to exit as soon as the test fails rather than processing all the characterss.

\$\endgroup\$
4
\$\begingroup\$

I’m going to do something a bit gauche and give you some new sample code. You’re using C-style arrays, which certainly have their place. But you’re using them without bounds checking.

This means, congratulations, you’ve written your first buffer overrun bug. There are thousands upon thousands of them. It’s the bug of the century. It happens to the best of us. (I don’t count myself among them, although I’ve done the same.) The engineers at Google caught a basically identical severe security bug in their codebase almost at the same moment you posted, So it is never too soon to get into the habit of not making them.

If you’re working with arrays,you’ve got to be extremely pedantic about always, always, always, checking the bounds of your array. Fortunately, there’s an easier way, which other people have suggested: use a dynamic string.

Reading a Dynamic String

Here’s a simple test driver. (Thanks to JDlugosz for the review of my code review!)

#include <cstdlib> // For EXIT_SUCCESS
#include <iostream>
#include <string>

// This should really be #include "palindrome.h"
extern constexpr bool is_palindrome(std::string_view);

using std::cin;
using std::cout;

int main()
{
    std::string s;
    
    while ( std::getline(  cin, s, '\n' ) ) {
        cout << ( is_palindrome(s)
                  ? "Palindrome.\n\n"
                  : "Not a palindrome.\n\n" );
    }
    
    return EXIT_SUCCESS;
}

This accepts spaces. If you only need to scan one word at a time, your main loop can consist of while (cin >> s).

Now, just implement is_palindrome, and you can test it with a script like the following:



Palindrome.

a
Palindrome.

ab
Not a palindrome.

eve
Palindrome.

adam
Not a palindrome.

madaminedenimadam
Palindrome.

When you’re done, hit either control-D on the Linux/Mac command line, or control-Z on Windows.

Writing the Palindrome Checker

Ignoring for the moment complications such as Unicode combining characters, case-sensitivity and whitespace, how could we safely and simply write is_palindrome()? Looking at the code you wrote, one way would be to convert the pointers and array references to iterators within the string. One quick optimization we can make: we do not need to scan the second half of the array and compare it again to the first half of the array. When we peel off all the layers and get to the center of the string, we can stop.

In other words, we want to compare the outer characters of our substring, return false if they do not match, then repeat for the substring with that outer pair removed, until we reach a substring of length 1 or 0.

How can we do this with STL containers? Here are three possible options, and you can do whichever of them looks best to you.

You can create a std::string_view of the string. This STL class gives you the member functions length() to return the length of the substring, front() to return the first character, back() to return the last character, and substr() to return a substring that can remove any number of characters from the front and back. These functions are sufficient to write your algorithm. Using a view of the string is much more efficient than copying the contents of the inner string into a new string.

You can also pass a pair of std::string::const_iterator arguments, named something like left and right, which are the left and right delimiters of the substring. You would call this as a helper function, originally with a substring consisting of the entire string. That is, bool is_palindrome(const std::string& s) be a one-liner that returns is_palindrome( s.cbegin(), s.cend()-1 ). In this case, you would test whether you reached the center by checking whether left and right have met in the middle, comparing them or subtracting right-left. You would test for mismatch by checking (*left != *right). After each check, you increment left and decrement right by 1, to give you the substring with the outer pair of characters removed. (This is almost identical to working with a start and an end pointer in C, but safer.)

Finally, you could pass in an iterator to the start of the string and a size_t length parameter, incrementing the start of the string and decrementing the length after each step.

It sounds like you want to solve the problem yourself, as a learning exercise, so I won’t write a solution for you, but any of those three approaches should work equally well. I would suggest you try writing it as a tail-recursive function. That is, you could make your function into an if/else if/else block with three branches, one of which returns true, one of which returns false and one of which returns a call to is_palindrome, passing the next-smaller substring as its argument or arguments. This is just as efficient as a for or while loop and, I find, easier to understand and debug.

For example, if we were using the implementation with iterators left and right that mark the first and last character of the substring, ignoring whitespace would mean adding the tests, at the appropriate place:

  // ...
} else if (std::isspace(*left)) { // Skip whitespace.
  return is_palindrome( left+1, right );
} else if (std::isspace(*right)) { // Skip whitespace here too.
  return is_palindrome( left, right-1 );
} else // ...

Which then makes the test driver detect madam in eden im adam and a man a plan a canal panama as palindromes. This, in my opinion, is more elegant than what you get if you try to refactor a for loop to add this feature. You could also write this very simply as a while loop—in this particular case, you could turn the branches into ++left and --right. The tail-recursive implementation, though, only ever modifies any local variables by making a tail-recursive call, and always specifies all of them, so you will find it much harder to write a bug where you accidentally modify one of them a second time or forget to update one of them.

Other Small Improvements

If you play your cards right, you can declare is_palindrome as a constexpr function and get constexpr bool eden = is_palindrome("madaminedenimadam"); to compile to constexpr bool eden = true;.

You could also potentially extend the algorithm to other kinds of containers than strings, using the ranges library of C++20. In this case, I’d say You Ain’t Going to Need It. If you ever needed to extend this to a production environment, the requirement would not be support for wstring or list<char>, but for UTF-8 and graphemes with canonical equivalence. Writing a palindrome checker that works on generic ranges or iterators, however, would be a good exercise to get comfortable with templates and concepts.

You might prefer std::next(s.cbegin()) and std::prev(s.cend()) from <iterator> to s.cbegin()+1 and s.cend()-1. The library functions also work for more types of iterator.

In production code, you might consider wrapping your palindrome library in a namespace and then putting using palindrome::is_palindrome; at the end of your header file. This has two advantages: it makes your code compatible with other modules written by great minds who named something the same way you did, and it lets you include things in the header that aren’t part of the public interface, such as helper function templates.

Finally, although I said that all the possible implementations should be equivalent, I found that current implementations of std::string_view are not quite as lightweight as advertised, and the compilers I tested do not optimize tail-recursive calls with std::string_view parameters as much as they optimize tail-recursive calls on an iterator pair.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ std::string(s); is strange. Why the parens around s being declared? \$\endgroup\$
    – JDługosz
    Dec 10 '21 at 15:09
  • 2
    \$\begingroup\$ The function should canonically use std::string_view for the parameter, rather than const std::string&. This is current best practice for C++17 and later. \$\endgroup\$
    – JDługosz
    Dec 10 '21 at 15:11
  • \$\begingroup\$ @JDługosz Good question. I think it’s actually a holdover from a refactoring where I had used std::string_view(s) as an initializer. \$\endgroup\$
    – Davislor
    Dec 10 '21 at 19:23
  • \$\begingroup\$ @JDługosz And good suggestion. It the underlying implementation uses a pair of iterators, it could even be a template that accepts any standard container. \$\endgroup\$
    – Davislor
    Dec 10 '21 at 19:25
  • \$\begingroup\$ @JDługosz The reason I didn’t use std::string_view as the parameter here was that I actually wrote a different ``string_view` version first, and tested it using an overload. In production code, you wouldn’t do that. \$\endgroup\$
    – Davislor
    Dec 10 '21 at 19:28
1
\$\begingroup\$

A quick look over the implementation from a C++ agnostic perspective gives a sense of confusion. The algorithm scans for palindromic characteristics of words until the checked length and presence of palindrome property a narrative more easily legible with different code formatting and use of variables:

bool palindrome = true;
int i = 1;
while ( i < a && palindrome )
{
    palindrome = ( word[i] == word[a - i - 1] );
    i++;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Why not a for-loop? \$\endgroup\$
    – greybeard
    Jan 11 at 18:47
0
\$\begingroup\$

Write some tests

You can't have good confidence in the code without testing it, and the best way to test is with a suite of repeatable tests that you can keep extending.

Start with a very simple test:

#include <cstdlib>

int main()
{
    return is_palindrome("a") ? EXIT_SUCCESS : EXIT_FAILURE;
}

That already forces us to extract the logic into a function, and separate it from the i/o:

bool is_palindrome(std::string_view /*not yet used */)
{
    return true;
}

We can write some more tests, adding a helper function:

int test_is_palindrome(const char *file, int line,
                       bool expected, std::string_view word)
{
    if (expected == is_palindrome(word)) {
        return true;
    }
    std::cerr << word << " should yield " << expected;
    return false;
}

int main()
{
    return test_is_palindrome(__FILE__, __LINE__, true, "a")
        +  test_is_palindrome(__FILE__, __LINE__, false, "ab")
        +  test_is_palindrome(__FILE__, __LINE__, true, "aba")
        +  test_is_palindrome(__FILE__, __LINE__, false, "abb")
        +  test_is_palindrome(__FILE__, __LINE__, true, "abba")
        +  test_is_palindrome(__FILE__, __LINE__, false, "abab")
        +  test_is_palindrome(__FILE__, __LINE__, false, "aaab")
        +  test_is_palindrome(__FILE__, __LINE__, false, "abaa");
}

We can build up more test cases, adjusting the implementation to make them pass as we do so. At some point, we'll need to decide what answer we want for an empty string (which is why I didn't start with that case).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.