Palindrome city

[kippwinger]

My teacher gave me the class for this program and the function definitions.
Basically, I need to read in words and determine whether or not they are palindromes.
I want to read in all the characters into stack One and stack Two ( I believe I have done that). I then want to reverse what is in stack Two and put it into stack Three. Then compare them. I am confused on how to reverse the order of chars in stack Two.

If anyone could help,that would be scrumtulescent.

#include <iostream.h>
#include <string.h>
#include <fstream.h>
#include <ctype.h>
#include <stdlib.h>

class stack
{
public:
	struct node;
	typedef node* nodeptr;
	struct node
	{ char c;
	nodeptr next;
	};
	stack();
	void makeStackEmpty();//deletes stack
	void push(char);//puts item on top of stack
	char pop();//takes off item on top and brings back what was there
	bool isEmpty();//is stack empty
	void print();//debugging
	private:
		nodeptr top;
};

stack::stack()
{top=0;
}

void stack::makeStackEmpty()//deletes stack
{
	nodeptr temp;
	temp=top;
	while(temp!=0)
	{
		top=top->next;
		delete temp;
		temp=top;
	}
}

void stack::push(char x)//puts item on top of stack
{
	nodeptr temp;
	temp=new node;
	temp->c=x;
	temp->next=top;
	top=temp;
}

char stack::pop()//takes off item on top and brings back what was there
{
	nodeptr temp;
	char x;
	if(isEmpty())
		cout << "error -- cannot pop from an empty stack\n";
	else
	{
		temp=top;
		x=top->c;
		top=top->next;
		delete temp;
	}
	return x;
}

bool stack::isEmpty()//is stack empty
{
	if(top==0)
		return true;
	else
		return false;
}

void stack::print()//prints
{
	stack t;
	char w;
	while(!isEmpty())
	{
		w=pop();
		cout << w << " ";
		t.push(w);
	}
	while(!t.isEmpty())
	{
		w=t.pop();
	}
	cout << endl;
}
//Globals
ifstream infile;
ofstream outfile;

//typedef char string[50];

//---------------------------------------------------------------------------//
int main()
{
	stack One, Two, Three;  //defines stacks
char x,temp;
infile.open("Pals.Dat", ios::nocreate);//open file to read from 
	if(!infile)
	{
		cout << "Error opening file" << endl;
		exit(1);
	}
	outfile.open("palindrome");//opens file ot be written to
while(infile)
{
infile.get(x);               //reads in characters
x=toupper(x);                //converts characters to upper case
if(ispunct(x)==0&&x!=' ')    // gets rid of punctuation
{
	One.push(x);
	Two.push(x);
	//Three.makeStackEmpty();
	temp=Two.pop();
	Three.push(temp);
	Three.print();
	//One.print();
	//Two.print();
	/*if()
	{
		cout << "is a palindrome" << endl;
	}*/
}
}
	return 0;

}
//--------------------------------------------------------------------------//

[ripper079]

am confused on how to reverse the order of chars in stack Two.

Pop stack two and push stack three (the poping character in stack two has to be pushed in stack three).

To find if a word is a palindrome simple compare stack one and stack three.

P.S. Easiest way for checking for a palindrome would be to use a string objects.

[kippwinger]

gotcha, thank you

[Perspective]

heres an example...

	.data
buf:	.space 256
good:	.asciiz "The string is a palindrome! \n"
bad:	.asciiz "The string is not a palindrome. \n"

	.text

main:	la	$a0, buf	#load the string into $a0
	li	$v0, 8		
	syscall	
		
	li	$t0, 0		#$t0 will be the string length counter
	b	tolower		#branch tolower to lowercase all chars
	
rmain1:	#point to return to main after tolower
	
	li	$t1, -1		#bottom character counter
	li	$t5, 1		#success indicator (1 for success, -1 else)
	b	check		#branch to check to see if string is a palindrome

rmain2:
	beq	$t5, -1, isnt	#if $t5 is -1, string is not a palindrome
	beq	$t5, 1, is	#if $t5 is 1, string is a palindrome

isnt:	la	$a0, bad	#load message 'bad'
	b	end		#branch to end
	
is:	la	$a0, good	#load message 'good'

end:	
	li	$v0, 4		#print result message
	syscall
	li	$v0, 10		#exit program
	syscall

tolower:
	#convert chars to lower case,
	#non-alphanum's to ~  (so they will be ignored),
	#and count the length of the string (stored in $t0)
	
	lb	$t1, buf + 0($t0)	#load a byte from the string
	beq	$t1, 0x00, rmain1	#if it is null, end of string is found
					#return to rmain1 to finish prog. execution 
	bgeu	$t1, 0x7b, nlow		#if byte is >= 0x7b it is not a lower case char  
	bleu	$t1, 0x60, nlow		#if byte is <= 0x60 it is not a lower case char
	
retlen:	#point to return after altering a byte
	sb	$t1, buf + 0($t0)	#store the final byte back in its location
	addi	$t0, $t0, 1		#add one to the string lenght counter
	b	tolower			#loop back to analyze next byte

nlow:	#not a lower case number
	bgeu	$t1, 0x5b, nalph	#if byte is >= 0x5b, it is not an alpha-num char
	bleu	$t1, 0x40, chnum	#if byte is <= 0x40, check and see if its a number
	add	$t1, $t1, 0x20		#other wise, its an upper-case letter, add 0x20 to
					#it to make it a lower case letter
	b	retlen			#return to the 'tolower' loop to store the byte

chnum:	#check to see if its a number
	bgeu	$t1, 0x3a, nalph	#if byte is >= 0x3a, it is not an alpha-num char
	bleu	$t1, 0x2f, nalph	#if byte is <= 0x2f, it is not an alpha-num char
	b	retlen			#otherwise, it is a lower case letter, just return
					#to the 'tolower' loop and leave byte unchanged
	
nalph:	
	li	$t1, 0x7e		#not alphanum, set to ~ so it will be ignored
	b	retlen

check:	#check if string is a palindrome

	addi	$t0, $t0, -1		#minus one from the top byte counter to init. it
	addi	$t1, $t1, 1		#add one to the bottom byte counter to init. it
	
	bleu	$t0, $t1, rmain2	#if the top counter is less then the bottom one,
					#return to main, comparing is done
rtop:	lb	$t2, buf + 0($t0)	#load top byte
	beq	$t2, 0x7e, nextop	#if top char is a '~' or a NULL, go to nextop 
	beq	$t2, 0x00, nextop	#to incriment the top counter
rbot:	lb	$t3, buf + 0($t1)	#same proceedure (as above) for the bottom char
	beq	$t3, 0x7e, nexbot
	beq	$t3, 0x00, nexbot

	beq	$t2, $t3, check		#if the chars are the same, go to top of loop
	
	li	$t5, -1			#else, set success indicator to -1 and go to rmain2
	b	rmain2

nextop:	addi	$t0, $t0, -1		#decrease top counter by one, go to rtop to load a 
	b	rtop			#new char

nexbot:	addi	$t1, $t1, 1		#increase top counter by one, go to rbot to load a
	b	rbot			#new char

errr... on second thought, go with the suggestions above

[kippwinger]

I tried to push the pop in stack two to stack three and it doesn't seem to be outputting correctly.

int main()
{
	int i=0;
	stack One, Two, Three;  //defines stacks
string x,temp;
//char x,temp;
infile.open("Pals.Dat", ios::nocreate);//open file to read from 
	if(!infile)
	{
		cout << "Error opening file" << endl;
		exit(1);
	}
	outfile.open("palindrome");

while(infile)
{
	i++;
	infile.get(x[i]);               

	x[i]=toupper(x[i]); 

	if(ispunct(x[i])==0&&x[i]!=' ')    
	{
		One.push(x[i]);
		Two.push(x[i]);
		Three.makeStackEmpty();
		temp[i]=Two.pop();
		Three.push(temp[i]);
		Three.print();
		
		/*if()
		{
		cout << "is a palindrome" << endl;
	}*/
	}
}
	return 0;

}

[quzah]

Here is the theory behind a 'three stack palindrome test':

while not done getting input
    s1.push( someinput );
    s2.push( someinput );

while s1.notEmpty( )
    s3.push( s1.pop( ) );

while s2.notEmpty( )
    if( s2.pop() != s3.pop() )
        ...not a palindrome...
...is a palindrome...

Quzah.

[kippwinger]

something like this?

s1.push( x[i] );
    s2.push( x[i] );

s1.isEmpty();

	s3.push( s1.pop( ) );


s2.isEmpty( );

	if( s2.pop() != s3.pop() )
        cout << "...not a palindrome..." << endl;
else
		cout << "...is a palindrome..." << endl;

I tried this and tried to see if the 3rd stack was in reverse order but it was not. The comparison is easy enough its just getting the 3rd stack formatted correctly that I having a problem with.

[quzah]

Originally posted by kippwinger
something like this?

s1.push( x[i] );
s2.push( x[i] );

//
// Look at my change:
// s1.isEmpty();
//
while( !s1.isEmpty( ) )
//
// Now you have the s3.push( s1.pop() );
//
	s3.push( s1.pop( ) );

//
// Look at my change here:
// s2.isEmpty( );
//
while( !s2.isEmpty( ) )
//
// Now you have your if statement.
//
	if( s2.pop() != s3.pop() )
        {
            cout << "...not a palindrome..." << endl;
            ...handle an error, ie: exit...
         }
//
// else
//
cout << "...is a palindrome..." << endl;

Something like that. See you have to loop through popping the elements off of the stack until they are empty. Otherwise, just having "s2.isEmpty()" by itself does nothing.

Quzah.

[kippwinger]

so,

//this reads in the characters into these 2 stacks

s1.push( x[i] );
s2.push( x[i] );

//while stack 1 is not empty

while( !s1.isEmpty( ) )

//take the first character off of stack one and push it to the top of 
//              stack 3?

	s3.push( s1.pop( ) );

//Then, while stack 2 is not empty, compare the 2 stacks to see if 
//         they are equal or not.

while( !s2.isEmpty( ) )

	if( s2.pop() != s3.pop() )
        {
            cout << "...not a palindrome..." << endl;
            ...handle an error, ie: exit...
         }
cout << "...is a palindrome..." << endl;

I implemented this and it printed out "..is a palindrome" over and over.. I understand what the functions do (somewhat) but how come it doesn't seem to be placing the elements that are popped off to the 3rd stack? Am I making this more complicated than it is?

Thanks for the help, by the way.

[quzah]

You'll want to change the end slightly. The point was, that if you added an exit statement right after you get to the "is not a palindrome" line, the main portion would stop, so it wouldn't continue to the "is a palindrome" line.

This was a fairly quick example. You'd want to tidy your example up. You'd want something like:

if( s2.isEmpty() && s3.isEmpty() )
    ...is a palindrome...
else
    ...something odd happened, one stack is not empty, which shouldn't happen...

What happens is this:
1) Fill two stacks, in order.
.... Use one of them later, so ignore it for now.
2) Pop each element of one stack, pushing it onto the third, empty stack.
... This causes that stack to hold the original information in reverse order.
3) Pop the first unused stack and the third stack, comparing each element.
... If at any time the element from one is not the same as the element from the other, it is not a plaindrome. Stop what you're doing now, there is no point in continuing.
4) If both stacks are empty now, and you are here, then in fact we have a palindrome.

Quzah.

[kippwinger]

thanks for your help. I will try that out.

[kippwinger]

Okay, I guess I need things explained to me like I'm a first grader.

I tried this code

s1.push( x[i] );
s2.push( x[i] );

s3.makeStackEmpty();

temp[i]=s1.pop();
s3.push(temp[i]);

s3.print();

and it printed out the elements in order like s1 and s2... not in reverse order.

????

[vasanth]

guys.. most if you here are crazy.. why the hell do you require two stacks if you are just gona reverse it and compare it.... you can just use a string or a char array... surely you are crazy and that is abusing the stacks purpose...

What you do is... you first push half of the elements into the stack then you pop the element and compare it with the next element.. if they dont match it is not a palindrrome but if they do.. you do it till the chars (elements get over) at the end if any element is left in the stack or a pop on an empty stack was tried it means the word is not a palindrome else it is...


THough your method would work.. that is not the way to use a stack.. use it the way is should be... else use a simple reverse to do that...

[kippwinger]

Thats the problem, I don't know how to use a "reverse" . the reason I'm using 3 stacks is because I need to output the original word that I read in.

any help with why that code above would not print out correctly would be cool. thanks

[laasunde]

I didnt read the whole thread but you could do something as simple as this :

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

int main()
{
    string buf;
    bool success=true;
    
    cout << "Enter string\t";
    getline(cin, buf);
    
    int beg = 0, end = (buf.length() - 1);  

    while( (beg <= end) && success)
    {
        char first = buf[beg];
        char last  = buf[end];
        if (first != last)
                success = false;
        
        beg++;
        end--;
    }
    if (success)
        cout << "The word is a palindrome" << endl;
    else
        cout << "The wors is NOT a palindrome" << endl;
    
    system("PAUSE");
}