Palindromes with stacks

Question

I'm creating a simple function to verify whether or not a string is a palindrome, and must use stacks in solving it.

bool isPalindrome(string word) {    
    // #1 determine length
    int n = word.size();

    // #3 make sure we have an even string
    if (n % 2 != 0)
        word.erase(0, 1);

    // #2 load the stack
    stack<char> s;
    for (int i = 0; i < n / 2; i++) {
        s.push(word[i]);
        word.erase(i, 1);
    }

    // #4 if our stack is empty, then return true
    if (s.empty())
        return true;

    // #5 compare the first & last letters for a valid palindrome
    /*if (s.top() == word[0]) {
        s.pop();
        word.erase(0, 1);
    } else
        return false;*/

    while (n != 0) {
        if (s.top() == word[0]) {
            s.pop();
            word.erase(0, 1);

            // return true only when our stack is empty
            if (s.empty())
                return true;
        } else
            return false;
    }
}

Is there a better way to do this? Are there any evident issues with the current state of the program?

Answer 1

First, a palindrome can have an odd number of characters:

Even-character palindrome: 1221
Odd-character palindrome: 13531

You only support even-character palindromes, which is bad, but even worse, you do not return an error about invalid input for an odd-digit palindrome, you remove the first digit.

Second, to help prevent errors, you should always use braces around one-liner if and loop statements:

if (n % 2 != 0) {
    word.erase(0, 1);
}

Third, don't leave dead code in there. You have a chunk of code commented out, so that should be removed.

Fourth, your comments are in the order of #1, #3, #2, ... Either the comments should be fixed or the code should be re-ordered.

Fifth, there is a mistake right here:

for (int i = 0; i < n / 2; i++) {
    s.push(word[i]);
    word.erase(i, 1);
}

Sixth, it appears that you are using namespace std; somewhere in your code as you did not prefix stack or string. This is not a good idea because namespaces can contain functions with the same name, so you can have problems with your code when you start using multiple namespaces, or even if you have a function in the same file that has the same name as a function in the namespace. You can read more about it here.

So, with the word "qweewq", you first remove "q" so the word is "weewq". Next, i == 1, so you remove "e", so the word is "wewq", and so on. You should change this to:

for (int i = 0; i < n / 2; i++) {
    s.push(word[0]);
    word.erase(0, 1);
}

This is a working solution:

bool isPalindrome(std::string word) {

    int wordSize = word.size();

    // #1 load the stack
    std::stack<char> s;
    for (int i = 0; i < wordSize / 2; i++) {
        s.push(word[0]);
        word.erase(0, 1);
    }

    // #2 make sure word size is same as stack size (handle odd-character palindromes)
    if (word.size() > s.size()) {
        word.erase(0, 1);
    }

    // #3 if our stack is empty, then return true
    if (s.size() == 0) {
        return true;
    }

    // #4 validate palindrome
    while (s.size() > 0) {

        if (s.top() == word[0]) {
            s.pop();
            word.erase(0, 1);

            // return true only when our stack is empty
            if (s.size() == 0 || word.size() == 0) {
                return true;
            }
        }
        else {
            return false;
        }
    }
}

Improvements on this solution are given here.

Answer 2

Note that n never changes in your while loop so you might as well have while(true)

Also note that there is no need to delete characters from word at any point. This would allow you to list word as a const reference in the function arguments (don't worry about this for now but it will matter to you at a later date).

Consider the following loop structure instead (for even palindromes):

for(int i = 0; i < n/2; i++)
{
    // do some stuff with word[i] and stack
}

for(int i = n/2; i < n; i++)
{
    // do some more stuff with word[i] and stack
}

Each iteration of these loops works with the exact same character your current loops work with but they don't waste time modifying word since it is unnecessary.

I'm guessing this is an assignment and the instructor made it simpler by not considering odd palindromes. If you need to do odd palindromes with the above loops then use the following:

for(int i = 0; i <= n/2; i++)
{
    // do some stuff with word[i] and stack
}

for(int i = n/2; i < n; i++)
{
    // do some more stuff with word[i] and stack
}

But this would require you to write separate (but nearly identical) code for when word has an even amount of characters and an odd amount of characters. You never want to do that. See if you can find a stopping value for the first loop that works in both odd and even cases.

Answer 3

In your last while, the condition is on n which is never updated in the loop, there is definitely something wrong with that (maybe not practically, but at least in design).

Except from the things already mentioned, the test on the length of the word could be done earlier (well, the test on the stack, but it's the same thing here).

Answer 4

This ended up being my final product. Worked 100%!

bool isPalindrome(string word) {    
    // #1 determine a constant length for our string
    int n = word.size();

    // #2 load the stack
    stack<char> s;
    for (int i = 0; i < n / 2; i++) {
        s.push(word[0]);
        word.erase(0, 1);
    }

    // #3 make sure we have an even string
    if (word.size() > s.size())
        word.erase(0, 1);

    // #4 if our stack is empty, then return true
    if (s.empty())
        return true;

    // #5 compare the first & last letters for a valid palindrome
    while (!s.empty()) {
        if (s.top() == word[0]) {
            s.pop();
            word.erase(0, 1);

            // return true only when our stack is empty
            if (s.empty())
                return true;
        } else
            return false;
    }
}