Помещение слова в стек и проверка его на наличие палиндрома

Наш учитель дал нам домашнее задание проверить палиндром слова, используя структуру данных «Стек».

Ниже приведен код, который я написал для следующей проблемы: -

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <stdbool.h>

struct Stack
{
    int top;
    int capacity;
    char *array;
};

void push(struct Stack stack, char a) //Push function.
{
    stack.array[++stack.top] = a; //Helps to push charater to a stack.
}

char pop(struct Stack stack) //Pop function.
{
    return stack.array[stack.top--]; //Helps to pop character from a stack.
}

int main(void)
{
    struct Stack original; //Original stack where the "Original" word will be pushed.
    original.top = -1;
    original.capacity = 10;
    original.array = calloc(original.capacity, sizeof(char));

    struct Stack checker; //Another stack that "Checks" whether the word is palindrome or not.
    checker.top = -1;
    checker.capacity = 10;
    checker.array = calloc(checker.capacity, sizeof(char));

    while(getchar()!='\0') //Getting all the characters from the stdin buffer and pushing it into "Original" stack.
    {
        push(original, getchar());
    }

    while(original.top != -1)
    {
        push(checker,pop(original)); //Popping from "Original" stack and pushing it to "Checker" stack.
    }

    while(checker.top != -1)
    {
        original.top = checker.top;
        if(original.array[original.top] != checker.array[checker.top]) //Checking every character in the stack if it is excatly same or not.
        {
            printf("It is not a palindrome.\n");
            return EXIT_SUCCESS;
        }
        else
        {
            checker.top = checker.top - 1;
        }
    }

    if(checker.top == -1)
    {
        printf("It is a palindrome.\n");
    }

    return 0;
}

Однако у меня возникает проблема в следующей строке: -

while(getchar()!='\0') //Getting all the characters from the stdin buffer and pushing it into "Original" stack.
{
    push(original, getchar());
}

Следующий цикл работает бесконечно. Моя цель добавления следующей строки состоит в том, что я хочу добавить отдельные символы из stdin buffer и push в стек original, пока он не встретит '\0'.

Что я здесь сделал не так? Это незаконно, чтобы сделать это таким образом?

Дополнение: -

Пример входных данных 1: - гражданский

Ожидаемый результат: - Это палиндром.

Образец входных данных 2: - мадам

Ожидаемый результат: - Это не палиндром.

P.S.

Следующий код: -

while(getchar()!='\0') //Getting all the characters from the stdin buffer and pushing it into "Original" stack.
{
    push(original, getchar());
}

теперь заменено на: -

int c;
int i = 0;

while ( i < original.capacity && ( c = getchar() ) != EOF && c != '\n' )
{
    push(original, c );
    ++i;
}

И теперь работает отлично, однако теперь для каждого слова мой код дает результат: -

Это палиндром.

Где я неправильно применил концепцию стека?


person Swarnim Khosla    schedule 27.09.2019    source источник
comment
Маловероятно, что getchar() читает '\0' из текстового файла. Мало того, вы выбрасываете прочитанный символ и нажимаете следующий.   -  person Weather Vane    schedule 27.09.2019
comment
@WeatherVane getchar() не может прочитать '\0' из stdin ?   -  person Swarnim Khosla    schedule 27.09.2019
comment
Да, может, если он есть, а в текстовом файле его нет. Строки заканчиваются новой строкой.   -  person Weather Vane    schedule 27.09.2019
comment
@WeatherVane, тогда какая может быть другая альтернатива?   -  person Swarnim Khosla    schedule 27.09.2019
comment
EOF означает конец файла/ввод   -  person KamilCuk    schedule 27.09.2019
comment
@WeatherVane разве это не должно быть char c?   -  person Swarnim Khosla    schedule 27.09.2019
comment
@SwarnimKhosla Нет. Прочтите документацию по функции.   -  person klutt    schedule 27.09.2019
comment
@SwarnimKhosla это ошибка новичка; предполагая, что символ должен быть char. Я думаю, что почти нет (если вообще есть) библиотечных функций, которые используют символы, которые принимают или возвращают тип char, обычно это int. Однако строка — это другое дело, обычно это массив char. В этом случае есть 256 возможных значений символов: но также есть EOF для представления.   -  person Weather Vane    schedule 27.09.2019


Ответы (1)


Эта петля

while(getchar()!='\0') //Getting all the characters from the stdin buffer and pushing it into "Original" stack.
{
    push(original, getchar());
}

в любом случае неправильно, потому что считывает символы дважды: в условии цикла и в теле цикла.

И вы должны явно ввести 0, например, с клавиатуры.

Вам нужно следующее

int c;
int i = 0;

while ( i < original.capacity && ( c = getchar() ) != EOF && c != '\n' )
{
    push(original, c );
    ++i;
} 

Также есть еще одна проблема. Эти функции имеют дело с копией переданных аргументов.

void push(struct Stack stack, char a) //Push function.
{
    stack.array[++stack.top] = a; //Helps to push charater to a stack.
}

char pop(struct Stack stack) //Pop function.
{
    return stack.array[stack.top--]; //Helps to pop character from a stack.
}

Вы должны объявить их как

void push(struct Stack *stack, char a) //Push function.
{
    stack-?array[++stack->top] = a; //Helps to push charater to a stack.
}

char pop(struct Stack *stack) //Pop function.
{
    return stack->array[stack->top--]; //Helps to pop character from a stack.
}

То есть передать исходный стек по ссылке через указатель.

И вызовите эти функции, например,

push( &original, c );

В противном случае вершина члена данных не будет изменена.

Вот ваша обновленная программа

# include <stdio.h>
# include <stdlib.h>

struct Stack
{
    int top;
    int capacity;
    char *array;
};

void push(struct Stack *stack, char a) //Push function.
{
    stack->array[++stack->top] = a; //Helps to push charater to a stack.
}

char pop(struct Stack *stack) //Pop function.
{
    return stack->array[stack->top--]; //Helps to pop character from a stack.
}

int main(void)
{
    struct Stack original; //Original stack where the "Original" word will be pushed.
    original.top = -1;
    original.capacity = 10;
    original.array = calloc(original.capacity, sizeof(char));

    struct Stack checker; //Another stack that "Checks" whether the word is palindrome or not.
    checker.top = -1;
    checker.capacity = 10;
    checker.array = calloc(checker.capacity, sizeof(char));

    int c;
    int i = 0;

    while ( i < original.capacity && ( c = getchar() ) != EOF && c != '\n' )
    {
        push( &original, c );
        ++i;
    }

    while(original.top != -1)
    {
        push(&checker,pop(&original)); //Popping from "Original" stack and pushing it to "Checker" stack.
    }

    while(checker.top != -1)
    {
        original.top = checker.top;
        if(original.array[original.top] != checker.array[checker.top]) //Checking every character in the stack if it is excatly same or not.
        {
            printf("It is not a palindrome.\n");
            return EXIT_SUCCESS;
        }
        else
        {
            checker.top = checker.top - 1;
        }
    }

    if(checker.top == -1)
    {
        printf("It is a palindrome.\n");
    }

    return 0;
}

Учтите, что эти заголовки

#include <string.h>
#include <stdbool.h>

являются избыточными.

person Vlad from Moscow    schedule 27.09.2019
comment
В упомянутом выше цикле я намереваюсь извлечь последний char из original стека и поместить его как первый char в стек checker, а затем сравнить их бок о бок с тем же номером индекса, как указано в if(original.array[original.top] != checker.array[checker.top]) - person Swarnim Khosla; 27.09.2019
comment
Предположим, что ввод 1 2 3. В стеке original порядок номеров будет 1 2 3. тогда как в стеке checker порядок будет 3 2 1. а потом я бы сравнил их рядом. - person Swarnim Khosla; 27.09.2019
comment
Еще один вопрос, не будем ли мы учитывать '\0' при перемещении char с stdin на original и с original на checker. - person Swarnim Khosla; 27.09.2019
comment
@SwarnimKhosla Если вы не введете его явно с помощью клавиатуры, он не будет отображаться во входном буфере. - person Vlad from Moscow; 27.09.2019
comment
разве '\0' не добавляется автоматически после каждого слова? Когда я использую fgets, он автоматически добавляется даже в scanf. - person Swarnim Khosla; 27.09.2019
comment
@SwarnimKhosla Нет, он не добавляется, потому что вы вводите отдельные символы вместо целой строки. - person Vlad from Moscow; 27.09.2019