Я пытался решить проблему строкового палиндрома, используя стек и очереди, но столкнулся с логическими проблемами - PullRequest
Новая
       25

Я пытался решить проблему строкового палиндрома, используя стек и очереди, но столкнулся с логическими проблемами

0 голосов
/ 11 апреля 2020

Вопрос: палиндром - это строка, которая читает одно и то же вперед и назад, например, радар, гудок и мадам. Задача состоит в том, чтобы написать алгоритм, который будет читать предложение слово за словом слева направо и решать, будет ли это палиндром. Строки палиндрома в качестве примера.

  • «Мадам, я - Адам.»
  • «Ева».

Алгоритм решения этой проблемы: относительно просто,

  • Использование стека и очереди.
  • Pu sh и добавление токенов (слов) в обе структуры данных.
  • Pop и Dequeue токены (слова) и сравнение.
  • Выполняйте операцию удаления, пока одна из структур данных не станет пустой. Если дело в том, что оба являются пустыми, предложение представляет собой палиндром.

Ваша задача - выяснить, является ли введенная пользователем строка палиндромом или нет. 

#include<iostream>
#include<string>
#include<stack>
#include<queue>
using namespace std;

#define MAX 1000

class Stack
{
    int top;
public:
    string myStack[MAX];

    Stack() { top = -1; }
    bool push(string item)
    {
        if (top >= (MAX - 1)) {
            cout << "Stack is full";
            return false;
        }
        else {
            myStack[++top] = item;
            cout << item << endl;
            return true;
        }
    }
    string pop()
    {
        if (top < 0) {
            cout << "Stack Underflow!!";
            return 0;
        }
        else {
            string item = myStack[top--];
            return item;
        }
    }
    bool isEmpty()
    {
     if (top == -1)
         return true;
     else
         return false;

    }
};

class Queue
{ public:
    string myqueue[MAX];
    int front, rear;
    Queue()
    {
         front = -1;
        rear = -1;
    }
    bool isFull() {
        if (front == 0 && rear == MAX - 1) {
            return true;
        }
        return false;
    }

    bool isEmpty() {
        if (front == -1) 
            return true;
        else 
            return false;
    }

    void enQueue(string item) {
        if (isFull()) {
            cout << endl << "Queue is full!!";
        }
        else {
            if (front == -1) front = 0;
            rear++;
            myqueue[rear] = item;
            cout << item << " "<<endl;
        }
    }
    string deQueue() {
        string value;
        if (isEmpty()) {
            cout << "Queue is empty!!" << endl;
            return false;
        }
        else {
            value = myqueue[front];
            if (front >= rear)
            {
                front = -1;
                rear = -1;
            }
            else {
                front++;
            }
            return(value);
        }
    }
};

int main()
{
    bool palindrome = true;
    Stack stack;
    stack.push("m");
    stack.push("a");
    stack.push("d");
    stack.push("a");
    stack.push("m");

    Queue queue;
    queue.enQueue("m");
    queue.enQueue("a");
    queue.enQueue("d");
    queue.enQueue("a");
    queue.enQueue("m");

    while (sizeof stack == 0 || sizeof queue == 0 )
    {
        stack.pop();
        queue.deQueue();
    };

    if (sizeof stack == sizeof queue )
    {
        cout << "The given word is palindrome." << endl;
    }
    else
    {
        cout << "The given word is not a palindrome." << endl;
    }

    system("pause");
    return 0;
}

1 Ответ

1 голос
/ 11 апреля 2020

Ах, волхвы c из sizeof.

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

Этот код 

while (sizeof stack == 0 || sizeof queue == 0 )

должен быть 

while (stack.isEmpty() || queue.isEmpty())

Вы написали ваши isEmpty методы, вы должны их использовать.

Но даже этот код неверен (из-за логических проблем). Я предполагаю (но не совсем уверен), что вы имели в виду 

while (!stack.isEmpty() && !queue.isEmpty())

Короче говоря sizeof не имеет места в этом коде. Если вам нужно знать размер ваших стеков или очередей, вы должны написать метод (называемый size возможно), который возвращает размер.

...