Palindrome city

This is a discussion on Palindrome city within the C++ Programming forums, part of the General Programming Boards category; My teacher gave me the class for this program and the function definitions. Basically, I need to read in words ...

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    81

    Palindrome city

    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.

    Code:
    #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;
    
    }
    //--------------------------------------------------------------------------//

  2. #2
    Veni Vidi Vice
    Join Date
    Aug 2001
    Posts
    343
    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.
    01000111011011110110111101100100 011101000110100001101001011011100110011101110011 01100100011011110110111001110100 01100011011011110110110101100101 01100101011000010111100101110011 0110100101101110 01101100011010010110011001100101
    Good things don´t come easy in life!!!

  3. #3
    Registered User
    Join Date
    Jun 2003
    Posts
    81
    gotcha, thank you

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    heres an example...

    Code:
    	.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

  5. #5
    Registered User
    Join Date
    Jun 2003
    Posts
    81
    I tried to push the pop in stack two to stack three and it doesn't seem to be outputting correctly.

    Code:
    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;
    
    }

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Here is the theory behind a 'three stack palindrome test':
    Code:
    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.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Jun 2003
    Posts
    81
    something like this?
    Code:
    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.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by kippwinger
    something like this?
    Code:
    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.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Jun 2003
    Posts
    81
    so,
    Code:
    //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.

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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:
    Code:
    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.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Jun 2003
    Posts
    81
    thanks for your help. I will try that out.

  12. #12
    Registered User
    Join Date
    Jun 2003
    Posts
    81
    Okay, I guess I need things explained to me like I'm a first grader.

    I tried this code
    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.

    ????

  13. #13
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    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...

  14. #14
    Registered User
    Join Date
    Jun 2003
    Posts
    81
    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

  15. #15
    Registered User
    Join Date
    Oct 2002
    Posts
    291
    I didnt read the whole thread but you could do something as simple as this :
    Code:
    #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");
    }

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Error in Recursive String Palindrome Code
    By clegs in forum C Programming
    Replies: 13
    Last Post: 12-21-2008, 12:36 PM
  2. Is it a Palindrome?
    By xp5 in forum C Programming
    Replies: 3
    Last Post: 09-06-2007, 06:26 AM
  3. Big help in Astar search code...
    By alvifarooq in forum C++ Programming
    Replies: 6
    Last Post: 09-24-2004, 12:38 PM
  4. Palindrome Coding trouble
    By TheLoneWolf32 in forum C++ Programming
    Replies: 3
    Last Post: 02-22-2003, 07:05 PM
  5. palindrome HELP !!!
    By TED22_8 in forum C Programming
    Replies: 23
    Last Post: 01-22-2002, 02:14 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21