Тестирование, если пользователь вводит строку, является палиндромом с использованием стеков

Question

Мой профессор хочет, чтобы мы написали программу, используя стеки и очереди, чтобы проверить, является ли введенная пользователем строка палиндромом. Я думаю, что я почти получил это, но это продолжает говорить, что каждое слово - палиндром.

Main:

#include <iostream>
#include "stack"
#include "queue"
#include "Palindrome.h"
using namespace std;

int main()
{
    string Pal;
    cout << "Enter a palindrome: ";
    getline (cin, Pal);

    TestPal test;

    test.isPalindrome(Pal);



    return 0;
}

Palindrome.h

#ifndef PALINDROME_H
#define PALINDROME_H
#include <iostream>
#include <string>
using namespace std;

class TestPal
{
    public: 
        int isPalindrome(string);
        TestPal();

};

#endif

Палиндром. c (я знаю, что просто иметь. c странно, наш профессор сказал нам обозначить это так)

#include "Palindrome.h"
#include "stack"
#include "queue"
#include <iostream>
#include <string>
using namespace std;

int TestPal::isPalindrome(string Pal)
{
    stack<char> Pstack;
    int length;
    int palSize = Pal.size();
    bool isPal;

    if(palSize > 0)
    {

        for(int i=0; i<palSize; i++)
        {
            Pstack.push(Pal[i]);
        }
    }


    for (int i = 0; i <= palSize; ++i)
    {
        if(Pstack.top() == Pal[palSize - i])
        {
            isPal = true;
            Pstack.pop();       
        }
        else
        isPal = false;
    }


  if(!isPal)
  {
    cout<< Pal << " is not a palindrome."<<endl;
  }
  else
  {
    cout<< Pal << " is a palindrome."<<endl;
  }

    //cout << palSize;

};

TestPal::TestPal()
{

};

Вывод

Enter a palindrome: Palindrome
Palindrome is a palindrome.

--------------------------------
Process exited after 12.39 seconds with return value 0
Press any key to continue . . .

Answer 1

В вашем коде было несколько ошибок:

• Ваш isPalindrome не вернул значение. Вы должны вернуть значение и проверить, является ли это значение истинным или ложным в вашей основной функции.
• Когда вы видите, что, например, первый символ не равен последнему, у вас есть немедленно вырваться из вашего l oop, поскольку, когда хотя бы одна пара символов не равна, у вас нет палиндрома, независимо от того, сколько из следующих символов равно.
• Pstack.top() возвращает последний символ вашей строки. Поэтому вы должны сравнить его с первым (Pal[i]), а не с последним.
• Сравнение не будет работать, если первый символ является заглавной буквой, а последний - нет. Поэтому я использовал функцию tolower, чтобы предотвратить эту проблему.
• if вокруг первого l oop не требуется, поскольку, если размер равен 0, тело for -l oop не будет выполняться в любом случае.
• Дальнейшая оптимизация: во втором l oop достаточно проверить первую половину строки.

Main

#include <iostream>
#include "stack"
#include "queue"
#include "Palindrome.h"
using namespace std;

int main() {
    string Pal;
    cout << "Enter a palindrome: ";
    getline(cin, Pal);

    TestPal test;

    if(test.isPalindrome(Pal)) {
        std::cout << Pal << " is a palindrome." << std::endl;
    } else {
        std::cout << Pal << " is not a palindrome." << std::endl;
    }



    return 0;
}

Палиндром

#include "Palindrome.h"
#include "stack"
#include "queue"
#include <iostream>
#include <string>
#include <ctype.h>

using namespace std;

int TestPal::isPalindrome(string Pal) {
    stack<char> Pstack;
    int palSize = Pal.size();

   for(int i = 0; i < palSize; i++) {
       Pstack.push(Pal[i]);
   }


    for(int i = 0; i < palSize / 2; ++i) {
        if(tolower(Pstack.top()) != tolower(Pal[i])) return false;

        Pstack.pop();
    }

      return 1;

};

TestPal::TestPal() {

};

Answer 2

Вы сказали: «Мой профессор хочет, чтобы мы написали программу , используя стеки и очереди ...»

Как говорит @molbdnilo в их комментарии , " Я подозреваю, что целью этого упражнения является то, что вы понимаете разницу между ними. "

Один из самых мощных инструментов в разработке алгоритма для решения проблемы - решить проблему самостоятельно - на бумага . Возьмите лист бумаги и напишите на нем «Стек» и «Очередь».

Stack   Queue
-----   -----

Теперь давайте возьмем первую букву «палиндрома» и добавим ее к обеим структурам:

Stack   Queue
-----   -----
  p       p

Чтобы добавить вторую букву палиндрома, помните, что она помещается в верхнюю часть стека (так что вам нужно будет сдвинуть "p" вниз), но для конец очереди:

Stack   Queue
-----   -----
  a       p
  p       a

Следующая буква в "палиндроме" - это "l" - добавьте ее в обе структуры:

Stack   Queue
-----   -----
  l       p
  a       a
  p       l

Сделайте это для остальной части слова.

Как только вы закончите - попробуйте снова со словом (или короткой фразой), что является палиндромом. Что ты заметил? Если бы я дал вам только кусочки бумаги, как бы вы использовали их, чтобы решить, какой именно палиндром?

PS

* * есть других (более эффективных) способов проверяя палиндромы, но ваш проф попросил использовать стек и очередь по определенной c причине.

Также - всегда помните, что если вы не знаете, как что-то сделать - ты не можешь научить компьютер это делать. И наоборот, как только вы сделали что-то самостоятельно (на бумаге), маленькими, простыми в описании шагами - кодирование становится намного проще.

Программирование состоит из нескольких шагов. Одним из них является разработка и понимание алгоритма. Отдельным шагом является написание кода для реализации алгоритма. Первый шаг может (и часто делает) занимать больше времени и усилий, чем второй.

Тратить больше времени, не отрывая руки от клавиатуры, чем на клавиатуру - это хорошо ^TM :)

Answer 3

Вот проверка палиндрома с использованием стека и одного без стека. Как вы можете видеть, последнее намного проще для чтения и понимания.

bool isPalindrome(std::string const& str)
{
    std::stack<char> tokens;
    for (std::size_t i = 0; i < str.size() / 2; i++)    
        tokens.push(str[i]);

    for (std::size_t i = (str.size() + 1) / 2; i < str.size(); i++)    
    {
        if (tokens.top() != str[i])
            return false;
        tokens.pop();
    }   

    return true;
}

bool isPalindromeWithoutStack(std::string const& str)
{
    std::stack<char> tokens;
    for (std::size_t i = 0; i < str.size() / 2; i++)
        if (str[i] != str[str.size() - 1 - i])
            return false;

    return true;
}

Функционально мы выводим sh каждый символ в тестовой строке в стеке. Мы делаем это до тех пор, пока не достигнем центра нашей тестовой строки (первое для l oop). После этого мы начинаем выталкивать стек и сравнивать извлеченный символ со следующим символом в тестовой строке (второй для l oop). Вычисление начального индекса (str.size() + 1) / 2 выглядит немного странно, но это позволяет нам пропускать символ в середине тестовой строки с неравной длиной (и, следовательно, средний символ не имеет с чем сравниваться).

Вторая версия isPalindromeWithoutStack просто сравнивает i-й символ с i-тым из конца.

Здесь является примером.