Palindrome Checker with Stack

Question

In my answer to this question, I wrote a new solution. Personally, I would not use a stack, but given that a stack was required, how good is this solution?

In this solution, I add half of the word, not including the middle character if applicable, to the stack and remove it from the string. If there is a middle character in the total string, the sizes of the string and the stack are not equal, and the middle character is at the beginning of the string, making it easy to delete (we don't need to compare it to itself, do we?). Then, I iterate through the stack, comparing the top of the stack to the beginning of the string; if they are equal, I remove the character from the stack and the string, and continue; otherwise, I return false;. If there are no characters left in the stack, I return true;.

bool isPalindrome(string word) {

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

    if (word.size() > s.size()) {
        word.erase(0, 1);
    }

    if (s.size() == 0) {
        return true;
    }

    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;
        }
    }
}

Answer 1

Your logic is incorrect in a few places. The first problem is that you are modifying word inside the loop so you probably want to cache the size before you use it in the loop indices. This is one of those insidious bugs.

int size = word.size();

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

if (word.size() > s.size()) {
    word.erase(0, 1);
}

I'm going to assume from here on that the cached size code above is what you intended the behavior of this program to be. Moving on to the next problem. Consider when word.size() is even, say 8. i will iterate from 0 to 4 inclusive. So s will have 5 characters and word will have 3. If word.size() was 9 then i would iterate from 0 to 4 as well, leaving word with 4 characters. Hence, after the loop, word.size() will never be greater than s.size(). In trying to handle the odd case you produced a bug in the even case. The loop bound you are looking for is:

for (int i = 0; i < size / 2; i++)

Here is the updated code for the first half:

int size = word.size();

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

if (word.size() > s.size()) {
    word.erase(0, 1);
}

Now you can verify that word.size() and s.size() will always be the same at this point. This means that inside the while loop you can remove the following check since s.size() and word.size() will both reach 0 at the same time:

if (s.size() == 0 || word.size() == 0) {
    return true;
}

Now the only way you can exit the loop is if all the letters on the stack and in the second half of the word were indeed the same. Which of course means that word is a palindrome. So just put a return true at the end.

You can now remove the following check before the while loop too since in this case the loop won't run and you will jump down to return true:

if (s.size() == 0) {
    return true;
}

With all of that said I think the code is a bit too complex. There is no need to modify word. With some integer arithmetic you can use two loops to iterate through word without deleting anything.

I will print out the loop indices for three looping methods you can use.

Method 1:

int i;
for(i = 0; i < n/2; i++)s.push(word[i]);
if(n % 2) i++; // skip the middle index if n is odd
for(; i < n; i++)  compare_stuff();

Method 2:

for(int i = 0; i < n/2; i++)s.push(word[i]);
for(int i = (n+1)/2; i < n; i++) compare_stuff(); // skip the middle index if n is odd

Method 3:

for(int i = 0; i < (n+1)/2; i++)s.push(word[i]);
for(int i = n/2; i < n; i++) compare_stuff();  // check the middle index against itself if n is odd

Method 2 is probably the best for this problem since it allows for local loop indices and doesn't check the middle value unnecessarily.

My code would be:

bool isPalindrome(const std::string& word)
{
    uint n = word.size();
    std::stack<char> s;

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

    for(uint i = (n+1)/2; i < n; i++)
    {
        if(s.top() != word[i])
        {
            return false;
        }

        s.pop();
    }

    return true;
}