Using a stack to determine if a string is a palindrome

I don't know how to create an isPalindrome() function and not sure if my getString() function is correct. I'm not sure what goes in there or how it would work. I've seen many questions like this on google but I can't seem to find one that would fit my scenario as the assignment has many restrictions - here is the assignment:

For the getString() function - Prompts the user to enter a string
Note: Use cin.get() in a while loop to read one character at a time.
The loop should stop when the enter key ('\n') is encountered.

parameters:
-pass the stack object by reference
-Pass the letters array

isPalindrome() - Compares the items on the stack to the items in the letters array.

parameters:
-pass the stack object by reference
-Pass the letters array

What I have so far...(bear in mind, I've already got a Stack.h file and a main.cpp file as well which aren't shown)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Stack::getString(Stack& letter, char& letters)
{
	char character;

	while (!letter.isFull())
	{
		cout << "Enter a string of characters: ";
		cin.get();
		if ("\n")
			break;
	}//is this function correct?
}

void Stack::isPalindrome(Stack& letter, char& letters)
{
//completely lost on this one
}
Last edited on
there are a couple of ways... you can push the first and last letter of your data and then pop pairs that should be equal, handle the odd character. Or you can push half the letters and then pop / check against the remaining chars (here too, beware the center letter). Either of those work.

While you may learn a little, this is like finding the area of a rectangle with calculus ... sigh. The way to do this if it were not dictated to you would be just iterate the string and compare elements until you know its not or finish and know it is. The stack just slows it down.
Last edited on
Thank you for the guidance jonnin, but what would that look like in code? Also, is my getString function OK?

That's what I'm saying! It's an obtuse method, and honestly, all the stuff online I've found isn't helping because they aren't as weird as my professor's directions.
letters array
char& letters

A reference to one character is not an array.


Lets say that you have two bags and you are given magic beans. Each bean is different.
Each bean replicates itself in your hand into two copies. You put one copy to each bag.
Both bags will have equal amount of beans.
That was the "getString".


The "isPalindrome".
You take one bean from each bag.
If they are equal, then you continue. Else if they are different, then you don't have a palindrome.
If you get all beans out without any pair being different, then you have a palindrome.


You are not using the cin.get() correctly. See http://www.cplusplus.com/reference/istream/istream/get/


How does the isPalindrome tell the result to the caller?


Why are these functions members of the Stack? They do get a stack as parameter. That is enough.
Here is my other code for those wondering...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//Stack.cpp
#include <iostream>
#include <fstream>
#include <string>
#include "Stack.h"
using namespace std;

Stack::Stack()
{
	top = -1; 
}

Stack::~Stack() {}

void Stack::makeEmpty()
{ 
	top = -1; 
}

bool Stack::isEmpty()
{
	return top == -1; 
}

bool Stack::isFull()
{
	return top == SIZE - 1;
}

void Stack::push(char letter)
{
	top++; letters[top] = letter;
}

void Stack::pop(char& letter)
{
	letter = letters[top]; top--;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//Stack.h
#pragma once
#include <iostream>
using namespace std;

const int SIZE = 99;

class Stack
{
private:
	char letters[SIZE];
	int top;
public:
	Stack();
	~Stack();
	void makeEmpty();
	bool isEmpty();
	bool isFull();
	void push(char letter);
	void pop(char& letter);
	void getString(Stack& letter, char& letters);
	void isPalindrome(Stack& letter, char& letters);
};
Last edited on
so it would be cin.get(letters)? i.e. getting them into the array?
It either displays on the console: "It is a palindrome!" or "It is not a palindrome..."
I understand that the isPalindrome pop's and then compares...I just don't know what that would look like for the function in concrete code...maybe something like this?
1
2
3
4
5
6
7
8
9
10
while (!letter.isEmpty())
{
letter.pop(letters)
    if (letter == letter2) //do I need two different char arrays?
        cout << "It is a palindrome!" << endl;

    else
         cout << "It is not a palindrome..." <<< endl;
}
cout << "here it is in reverse: " << letters;


Please help, am very lost.
Last edited on
what is in your stack if you input this string: "a dog a panic in a pagoda"
(don't do this by hand, run your code with an example and show the input and the stack to us). If you need more sample data, grab the rest of the lyrics from bob by weird al.
Last edited on
Here is my updated functions - thanks for the help, again, but I'm running into a pesky logic error:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void Stack::getString(Stack& letterstack, char (&letterarray)[SIZE])
{
	cout << "Enter a string of characters: ";

	while (sizeof(letterarray) != SIZE)
	{
		cin.get(letterarray, SIZE);
		if ("\n")
			break;
	}
	
	for (int i = 0; i < SIZE; ++i)
	{
		letterstack.push(letterarray[i]);
	}
	
}

void Stack::isPalindrome(Stack& letterstack, char(&letterarray)[SIZE])
{
	char popletter;
	cout << "Here it is in reverse: ";
	while (!letterstack.isEmpty())
	{
		for (int i = 0; i < SIZE; i++)
		{
			letterstack.pop(popletter);
			cout << popletter;
			if (popletter == letterarray[i])
			{
				return;
			}
			else
				cout << "It is not a palindrome...";
		}
	}
	cout << "It is a palindrome!";
}


Here is the output:
Enter a string of characters: Here it is in reverse: ╠

I can't seem to make the program take in user input. This logic error just prints the cout portion but actually doesn't take in anything from the user. Thanks again.
1
2
if ("\n")
  break;

IF what?

The "\n" is a literal string constant. You effectively get its address, like you would write:
1
2
const char* ptr = "\n";
if ( ptr )

The content of the literal in irrelevant here.
The address of literal is not null.
Null evaluates to false, not null to true

In other words, you could have written:
1
2
3
4
5
if ( true )
  break;

// or simply
break;

That is useless in two ways. The second being that your cin.get never reads a newline.


getString( Stack& letterstack, char (&letterarray)[SIZE] )
A reference to array. Why?

sizeof(letterarray)
If you are looking for how many characters you did get, then that is not the way.


Here are two approaches to get String:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int getString( Stack& letterstack, char letters[], int SIZE )
{
  char ch = 0;
  int count = 0;
  while ( count < SIZE && std::cin.get(ch) && ch && ch != '\n' )
  {
    letterstack.push( ch );
    letters[count++] = ch; // letters will not contain null
  }
  return count;
}

void getString( Stack& letterstack, char letters[], int SIZE )
{
  std::cin.get( letters, SIZE ); // letters will contain a null
  while ( *letters )
  {
    letterstack.push( *letters );
  }
}
I refactored my code per your suggestions, and I get no runtime errors on the getString function. However, I am getting two "too few arguments in function call" errors and I don't know how to resolve it. I tried putting in: "(Stack& letterstack, char letterarray[], int SIZE)" however that did not resolve it. Can you guide me on what the proper parameters for the calls are, I know for a fact there are two parameters needed? Thank you.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <fstream>
#include <string>
#include "Stack.h"
using namespace std;

int main()
{
	Stack stack;
	
	stack.getString();//too few arguments in function call
	stack.isPalindrome();//too few arguments in function call
}


EDIT: I've been able to get no runtime errors with "stack.getString(letterstack, letterarray, SIZE);" HOWEVER, I get errors elsewhere. That is to say, I put
"Stack &letterstack;
char letterarray[];"

before main, and it's saying that I didn't initialize the reference (for Stack& letterstack;). So I'm still lost here.
Last edited on
For the getString() function - Prompts the user to enter a string
Note: Use cin.get() in a while loop to read one character at a time.
The loop should stop when the enter key ('\n') is encountered.

parameters:
-pass the stack object by reference
-Pass the letters array

isPalindrome() - Compares the items on the stack to the items in the letters array.

parameters:
-pass the stack object by reference
-Pass the letters array

It doesn’t seem isPalindrome is required to be a method of class stack, does it?
Is it required in the part of the assignment you didn’t post?

Let’s see if we agree about what the assignment requires:
a) A stack works this way: when you put an element into the stack, that element prevents the previous one to be accessed - it’s a LIFO (last in - first out) container.
It means you can only access the last element inserted (or the top element, whatever you want to call it).
The only way to access elements in a stack is to remove them one by one, starting from the last.

So, if you put a sequence of characters (usually called a string) inside a stack, when you pull them out, what you get is the original sequence (string) in reverse order.


b) When people speak about palindromes, it is implicit that spaces are not taken into account and also the string must be ‘case insensitive’.


c) If you put a string into a stack and later

--> you compare your original string, character by character from left to right, to what you pop out from the stack, you are actually

--> comparing your string characters left to right to your string characters right to left


So, what your assignment requires is:
- Purpose: ask the user a string and discover if it is palindrome.

Steps:
- Inside a getString() function, ask the user a string

- Read it character by character (by means of std::cin.get)

- Since you are reading it character by character, you can save it both in a ‘normal’ string container (a std::string, a C-Style array…) and in a stack.

- It implies that getString() function should ‘be aware’ both of a string container and of a stack.

- Remember you don’t need to save all characters!!
(Note: you can begin by writing a simpler version of your function which takes all characters and then test it by passing strings that have neither spaces nor uppercase letters - later you can develop the complete version)

- In a isPalindrome() function,
define a loop that reads one character from the string and pops one character from the stack and compares them.
If all the characters match, state the string is palindrome.

Happy coding!

Please read the tutorials about
functions: http://www.cplusplus.com/doc/tutorial/functions/
arrays: http://www.cplusplus.com/doc/tutorial/arrays/

That is to say, I put
"Stack &letterstack;
char letterarray[];"
before main, and it's saying that I didn't initialize the reference ...

1. "before main" is usually a global variable.
They should be used only when they must be used. That is almost never.


2. int& data; The data is a reference. Reference must always point to a real variable.
void func( int& param ); the param is a reference too. We must call the function with argument that the param can point to.
1
2
int answer = 42; // real integer variable
func( answer ); // during this function call the param is a reference to the answer 



3. The size of array must be known when you compile the code. The size must be a compile-time constant.
char letterarray[];
How many elements do we declare that the array letterarray contains?
Error: there is no number in the brackets []

This is ok: char letterarray[] = "Hello";
The compiler can count the characters in the initializer and use that number (6) for the size of the array.

Function parameters a slightly different. When you call function with array argument, there is no copying of the contents of the array into the array parameter of the function. The function will see the caller's array.

In fact,
1
2
void func( int* param );
void func( int param[] );

These declarations are identical for the compiler.
The latter syntax merely hints to the user that the function expects an array.
Trying to glean from your post and the articles on how to rejigger it, I came up with the following:

1
2
3
4
5
6
7
8
9
int main()
{
        Stack stack;
	char letterstack = 0;
	char letterarray[SIZE];

	stack.getString(letterstack, letterarray, SIZE);//error under letterstack "cannot be initialized with value of type char"
	stack.isPalindrome(letterstack, letterarray, SIZE);//error under letterstack
}


However, this does not work as I get errors. It may have to do with char being passed as an int, I think. But honestly I've tried almost everything to get it to work. I have been playing whack-a-mole with the errors for hours...Any way to fix this? Thanks again for your help.
Last edited on
What is the type of the first parameter of the getString? Is it a reference to Stack?

What is the type of the first argument that you call the function with?
You call it with 'letterstack'. The type of 'letterstack' is char.

Is char a Stack? No.

1
2
3
4
5
6
7
8
int main()
{
        Stack stack;
	char letterarray[SIZE];

	stack.getString( stack, letterarray, SIZE );
	stack.isPalindrome( stack, letterarray, SIZE );
}



Why are the getString and isPalindrome still member functions of class Stack?
That makes no sense. None at all.

Nothing in the instructions that you have shown says that they should be members.


PS. When you get "an error", please show the error message as completely and exactly as possible. That helps everybody. Most of all you.
thank you everyone who helped me. also thanks to keskiverto to guiding me towards the finish line.
Topic archived. No new replies allowed.