C++ 递归和指针问题

Question

首先，这是作业。

需要什么：

1.Take in string input
2. copy string (stripping out white space, punctuation, and 
   covert all characters to uppercase in the process)
3. Then determine if this copied string is a palindrome.

判断回文所需的方法：

Base Case:  string length is <= 1
General Case: if first letter != last letter, false, otherwise
               point to next letter and write '[=11=]' to last letter and
               call the method again

例如：

RACECAR[=12=]   R==R
ACECA[=12=]     A==A
CEC[=12=]       C==C
E[=12=]         E <= 1  TRUE!

我的 isPalindrome 函数无法正常工作。据我所知，其他一切都很好。我真的认为问题出在我的递归调用上。我已经调试了 2 天了，但我不明白为什么 return 是错误的。任何帮助将不胜感激。我不是在找人帮忙，也许只是想多看看这段代码。谢谢

#include <iostream>
#include <string>
#include <cctype>   
using namespace std;

int charCount(char  * copy)
{
    int count = 0;

    for (int i = 0; copy[i] != '[=13=]'; i++)
    {
        count++;
    }

    return count;
}

bool isPalindrome(char *copy)
{
    bool result = false;
    int size = charCount(copy);

    char * last = &copy[size - 1];

    if (size <= 1)
    {
        result = true;
    }

    if (copy != last)
    {
        result = false;
    }

    else
    {
        ++copy;
        last = '[=13=]';
        isPalindrome(copy);
    }

    return result;
}

void stringCopy(char * source, char * destination)
{
    int sourceIndex = 0;
    int destIndex = 0;

    while (source[sourceIndex] != '[=13=]')
    {
        while (!(isalnum(source[sourceIndex])) && source[sourceIndex] != '[=13=]')
        {
            sourceIndex++;
        }

        if (source[sourceIndex] == '[=13=]')
        {
            break;
        }

        if (isalpha(source[sourceIndex]))
        {
            destination[destIndex] = toupper(source[sourceIndex]);
        }

        if (isdigit(source[sourceIndex]))
        {
            destination[destIndex] = source[sourceIndex];
        }

        sourceIndex++;
        destIndex++;
    }

    destination[destIndex] = '[=13=]';
}

int main()
{
    string input = "";

    cout << "Enter a string: ";
    getline(cin, input);

    char * source = &input[0];
    int sourceSize = charCount(source);

    char * copy = new char[sourceSize];

    stringCopy(source, copy);

    int copySize = charCount(copy);

    if (isPalindrome(copy))
    {
        cout << input << " is a palindrome!" << endl;
    }

    else
    {
        cout << input << " is not a palindrome" << endl;
    }

    return 0;
}

Answer 1

四个错误

首先你有三个案例，但你只想执行一个，所以它应该是一个单一的 if ... else if ... else ... 语句，而不是你拥有的 if ... if ... else ... 语句。

其次，您的比较不正确，因为您比较的是指针，而不是它们指向的字符。

第三个错误与第二个类似，当您尝试缩短分配给指针而不是字符的字符串时。

最后您忘记将递归调用的结果分配给您的 result 变量。相当常见的新手错误。

这是我的努力（未经测试的代码）

bool isPalindrome(char *copy)
{
    bool result = false;
    int size = charCount(copy);

    char * last = &copy[size - 1];

    if (size <= 1)
    {
        result = true;
    }
    else if (*copy != *last) // else if and *copy != *last, not copy != last
    {
        result = false;
    }
    else
    {
        ++copy;
        *last = '[=10=]'; // *last not last
        result = isPalindrome(copy); // capture return value from recursive call
    }

    return result;
}

一个函数中的四个错误可能看起来很多，但这些都是很容易修复的愚蠢错误。整体代码质量还是不错的。

现在为了加分，看看您是否可以编写一个不会破坏字符串的版本。因为您分配了 *last = '[=14=]'，所以您在工作时更改了字符串。

Answer 2

复制 != 最后一个

这些变量是指向 char 的指针。您需要在比较之前取消引用它们。

尝试： *复制！= *最后

Answer 3

本文不针对您代码中的任何问题，也不说明如何根据作业编写代码。此处的代码只是为了完整性，以展示如何使用 c++ 已经提供的工具解决问题，而无需重新发明轮子。

std::copy_if 和 std::transform 是您的 stringCopy，带有向后和向前运算符的 std::equal 基本上就是您在 isPalindrome 中所做的。在这种情况下使用递归无论如何都不是一个好主意。

#include <string>
#include <algorithm>
#include <iostream>


bool is_palindrom( const std::string &input ) {
    std::string copy;

    // copy everything except spaces and punctations using:
    // copy_if, isspace and ispunct
    std::copy_if(input.begin(), input.end(), std::back_inserter(copy), [] (int ch) -> bool {
        return !::isspace(ch) && !::ispunct(ch);
    });

    // transform to uppercase
    std::transform(copy.begin(), copy.end(), copy.begin(), ::toupper);

    // check if palindrom using iterators and revers iterators
    // copy.end()  - halfway is valid as std::string::iterator is a random access iterator
    size_t halfway = copy.size() / 2;
    bool isPalindrom = std::equal(copy.begin(),  copy.end()  - halfway, 
                                  copy.rbegin(), copy.rend() - halfway);

    return isPalindrom;
}

int main() {
    std::cout <<  is_palindrom("2aba2")  << std::endl; // 1
    std::cout <<  is_palindrom("2 ab a2")  << std::endl; // 1
    std::cout <<  is_palindrom("2 abb a2")  << std::endl; // 1
    std::cout <<  is_palindrom("abca")  << std::endl; // 0
}

C++ 递归和指针问题

C++ Recursion and Pointer Problems

c++

recursion

pointers

palindrome