Thread: Palindrome

  1. #1
    Registered User
    Join Date
    Feb 2009
    Location
    Indiana
    Posts
    99

    Palindrome

    Write a program that uses both a Stack and a Queue to determine if a number of lines in Text File are packed palindromes or not. A packed palindrome is a sequence of characters with the property: If we remove all the characters except the letters (you may assume all capitals), then the resulting string when reversed is the same as it was before reversal.

    Restrictions: You must use the Circular Array Implementation of the Queue. You may choose which implementation you want for the Stack.


    Im stuck bc I need to say when it is a Palindrome and when I run it it's out of range.

    Code:
    #include<iostream>
    #include<conio.h>
    #include<string>
    #include<ctype.h>
    using namespace std;
    
    const int DefaultListSize = 50;
    typedef char Elem;
    
    class Astack 
    {
    private:
    	int top;	/*Index for top element*/
    	int size;	/*Maximum size of stack*/
    	Elem*listArray;	/*Array holding stack elements*/
    public:	
    		Astack(int sz =DefaultListSize)	/*Constructor*/
    		{size = sz; top = 0; listArray = new Elem[sz];}
    		~Astack() { delete [] listArray;}	/*Destructor*/
    		void clear() {top = 0;}
    		bool push(const Elem& item){
    			if(top == size) return false;	/* Stack is full*/
    			else {listArray [top++] = item;
    				return true;
    			}
    		}
    		bool pop(Elem& item){	/*Pop top element*/
    			if(top == 0) return false;
    			else {item = listArray[--top]; 
    				return true;
    			}
    		}
    		bool topValue(Elem& item) const {	/*Return top element*/
    			if (top == 0) return false;
    			else {item = listArray[top - 1];
    			return true;
    			}
    		}
    		int length() const {return top;}
    		bool IsEmpty() const {if(top == 0) return true;
    		else return false;
    		}
    	};
    
    class AQueue
    {
    private:
    	int size;	/*Maximum size of queue*/
    	int front;	/*Index of front element*/
    	int rear;	/*Index of rear element*/
    	Elem*listArray;	/*Array holding queue elements*/
    public:
    	AQueue(int sz =DefaultListSize){	/*Constructor*/
    		size = sz + 1;
    		rear = 0;
    		front = 1;
    		listArray = new Elem[size];
    	}
    	~AQueue() {delete [] listArray; }	/*Destructor*/
    	void clear() {front = rear; }
    	bool enqueue(const Elem& it) {
    		if(((rear+2) % size) == front) return false; /*Full*/
    		rear = (rear+1) % size;	/*Circular increment*/
    		listArray[rear] = it;
    		return true;
    	}
    	bool dequeue(Elem& it) {
    		if (length() == 0) return false;	/*Empty*/
    		it = listArray[front];
    		front = (front+1) % size;	/*Circular increment*/
    		return true;
    	}
    	bool frontValue(Elem& it) const {
    		if (length() == 0) return false; /*Empty*/
    		it = listArray[front];
    		return true;
    	}
    	virtual int length() const
    	{ return ((rear+size) - front+1) % size; }
    };
    
    int main()
    {
    	Astack S;
    	AQueue Q;
    	string s;
    	int i = 0;
    
    	cout << "Enter String" << endl;
    	getline(cin, s);
    
    	for(i = 0; i < s.length(); i++){
    		cout << s.at(i);
    		while(s.at(i) != NULL){
    			S.push(s.at(i));
    			Q.enqueue(s.at(i));
    			i++;	/*Get next character*/
    		}
    		while(s.at(i) == NULL){
    			if(S.topValue(s.at(i)) != Q.frontValue(s.at(i)))
    				cout << "It is not a Palindrome";
    			else 
    				S.pop(s.at(i));
    				Q.dequeue(s.at(i));
    		}
    	}
    	return 0;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You really really really want to look more carefully here:
    Code:
    S.topValue(s.at(i)) != Q.frontValue(s.at(i))
    Hints: What are you comparing with the != (answer to hint: the return values of the function calls. New hint: what are they)? What does calling topValue(s.at(i)) actually do to s.at(i)? Similarly with Q.frontValue(s.at(i)).

  3. #3
    Registered User
    Join Date
    Feb 2009
    Location
    Indiana
    Posts
    99
    I still dont see whats wrong with that. I want to compare the top value in the stack with the front value in the Queue bc if they are the same then I should pop them then repeat. Or should I pop them into a variable and then compare the variables?
    Here's my new code so far:
    Code:
    #include<iostream>
    #include<string>
    #include<ctype.h>
    using namespace std;
    
    const int DefaultListSize = 50;
    typedef char Elem;
    
    class Astack 
    {
    private:
    	int top;	/*Index for top element*/
    	int size;	/*Maximum size of stack*/
    	Elem*listArray;	/*Array holding stack elements*/
    public:	
    		Astack(int sz =DefaultListSize)	/*Constructor*/
    		{size = sz; top = 0; listArray = new Elem[sz];}
    		~Astack() { delete [] listArray;}	/*Destructor*/
    		void clear() {top = 0;}
    		bool push(const Elem& item){
    			if(top == size) return false;	/* Stack is full*/
    			else {listArray [top++] = item;
    				return true;
    			}
    		}
    		bool pop(Elem& item){	/*Pop top element*/
    			if(top == 0) return false;
    			else {item = listArray[--top]; 
    				return true;
    			}
    		}
    		bool topValue(Elem& item) const {	/*Return top element*/
    			if (top == 0) return false;
    			else {item = listArray[top - 1];
    			return true;
    			}
    		}
    		int length() const {return top;}
    		bool IsEmpty() const {if(top == 0) return true;
    		else return false;
    		}
    	};
    
    class AQueue
    {
    private:
    	int size;	/*Maximum size of queue*/
    	int front;	/*Index of front element*/
    	int rear;	/*Index of rear element*/
    	Elem*listArray;	/*Array holding queue elements*/
    public:
    	AQueue(int sz =DefaultListSize){	/*Constructor*/
    		size = sz + 1;
    		rear = 0;
    		front = 1;
    		listArray = new Elem[size];
    	}
    	~AQueue() {delete [] listArray; }	/*Destructor*/
    	void clear() {front = rear; }
    	bool enqueue(const Elem& it) {
    		if(((rear+2) % size) == front) return false; /*Full*/
    		rear = (rear+1) % size;	/*Circular increment*/
    		listArray[rear] = it;
    		return true;
    	}
    	bool dequeue(Elem& it) {
    		if (length() == 0) return false;	/*Empty*/
    		it = listArray[front];
    		front = (front+1) % size;	/*Circular increment*/
    		return true;
    	}
    	bool frontValue(Elem& it) const {
    		if (length() == 0) return false; /*Empty*/
    		it = listArray[front];
    		return true;
    	}
    	virtual int length() const
    	{ return ((rear+size) - front+1) % size; }
    };
    
    int main()
    {
    	Astack S;
    	AQueue Q;
    	string p;
    	unsigned int i = 0;
    	int count = 0;
    	int mismatch = 0;
    
    	cout << "Enter Palindrome" << endl;
    	getline(cin, p);
    
    	for(i = 0; i < p.length(); i++){
    		if(ispunct(p[i]))
    			p.erase(i);
    		while(p.at(i) != EOF){
    			S.push(p.at(i));
    			Q.enqueue(p.at(i));
    			i++;	/*Get next character*/
    			count++;
    	}
    	}
    	while(count > 0){
    		if(S.topValue(p.at(i)) == Q.frontValue(p.at(i)))
    		S.pop(p.at(i));
    		Q.dequeue(p.at(i));
    		mismatch++;
    		count--;
    	}
    	if(mismatch < 0)
    		cout << "It is a Palindrome";
    	else
    		cout << "It is not a Palindrome";
    	return 0;
    }

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by jturner38 View Post
    Or should I pop them into a variable and then compare the variables?
    You ask this question as if you had a choice. Your topValue and dequeue functions do NOT return the top/front value from your stack/list -- they return either true or false. So writing
    Code:
    S.topValue(s.at(i)) != Q.frontValue(s.at(i))
    merely compares true to true (or false to false) -- since the stack/queue have the same number of items in them, this will always be false. You will need to look at the elements themselves -- the elements aren't returned, but are passed back via the argument.

  5. #5
    Registered User
    Join Date
    Feb 2009
    Location
    Indiana
    Posts
    99
    I finally got it! Here's my final code if anybody wants to see it.
    Code:
    #include<iostream>
    #include<string>
    #include<ctype.h>
    using namespace std;
    
    const int DefaultListSize = 50;
    typedef char Elem;
    
    class Astack 
    {
    private:
    	int top;	/*Index for top element*/
    	int size;	/*Maximum size of stack*/
    	Elem*listArray;	/*Array holding stack elements*/
    public:	
    		Astack(int sz =DefaultListSize)	/*Constructor*/
    		{size = sz; top = 0; listArray = new Elem[sz];}
    		~Astack() { delete [] listArray;}	/*Destructor*/
    		void clear() {top = 0;}
    		bool push(const Elem& item){
    			if(top == size) return false;	/* Stack is full*/
    			else {listArray [top++] = item;
    				return true;
    			}
    		}
    		bool pop(Elem& item){	/*Pop top element*/
    			if(top == 0) return false;
    			else {item = listArray[--top]; 
    				return true;
    			}
    		}
    		bool topValue(Elem& item) const {	/*Return top element*/
    			if (top == 0) return false;
    			else {item = listArray[top - 1];
    			return true;
    			}
    		}
    		int length() const {return top;}
    		bool IsEmpty() const {if(top == 0) return true;
    		else return false;
    		}
    	};
    
    class AQueue
    {
    private:
    	int size;	/*Maximum size of queue*/
    	int front;	/*Index of front element*/
    	int rear;	/*Index of rear element*/
    	Elem*listArray;	/*Array holding queue elements*/
    public:
    	AQueue(int sz =DefaultListSize){	/*Constructor*/
    		size = sz + 1;
    		rear = 0;
    		front = 1;
    		listArray = new Elem[size];
    	}
    	~AQueue() {delete [] listArray; }	/*Destructor*/
    	void clear() {front = rear; }
    	bool enqueue(const Elem& it) {
    		if(((rear+2) % size) == front) return false; /*Full*/
    		rear = (rear+1) % size;	/*Circular increment*/
    		listArray[rear] = it;
    		return true;
    	}
    	bool dequeue(Elem& it) {
    		if (length() == 0) return false;	/*Empty*/
    		it = listArray[front];
    		front = (front+1) % size;	/*Circular increment*/
    		return true;
    	}
    	bool frontValue(Elem& it) const {
    		if (length() == 0) return false; /*Empty*/
    		it = listArray[front];
    		return true;
    	}
    	virtual int length() const
    	{ return ((rear+size) - front+1) % size; }
    };
    
    
    int main()
    {
    	Astack S;
    	AQueue Q;
    	string p;
    	char str1;
    	char str2;
    	unsigned int i;
    
    	cout << "Enter what you think is a Palindrome:\n";
    	getline(cin, p);
    
    	for(i = 0; i < p.length(); i++){
    			if(p.at(i) != '\0'){
    				if(('A' <= p.at(i)) && (p.at(i) <= 'Z')){
    					S.push(p.at(i));
    					Q.enqueue(p.at(i));
    				}
    			}
    	}
    
    	while(!S.IsEmpty()){
    		S.pop(str1);  
    		Q.dequeue(str2);
    		cout << str1 << str2 << ' ';
    	}
    	if(str1 == str2)
    		cout << "\n It is a Packed Palindrome" << endl;
    	else
    		cout << "\nIt is not a Packed Palindrome" << endl;
    	return 0;
    	
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Palindrome Problems
    By obeygiant in forum C Programming
    Replies: 14
    Last Post: 11-21-2009, 10:49 AM
  2. Error in Recursive String Palindrome Code
    By clegs in forum C Programming
    Replies: 13
    Last Post: 12-21-2008, 12:36 PM
  3. bool palindrome definition
    By justinc911 in forum C++ Programming
    Replies: 3
    Last Post: 11-26-2003, 05:50 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