CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: Palindrome

  1. #1
    Join Date
    Nov 2010
    Posts
    36

    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 because I need to figure out how to compare the letters because when u push and dequeue off the stack and queue if 1 of those doesnt match then it will never be a palindrome. But I dont what to say. Should I compare the top value with the front vale or should I some how pop them into a variable and then compare them?

    Here's what I got so far:
    Code:
    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 match = 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){
    		S.pop(p.at(i));
    		Q.dequeue(p.at(i));
    
    		count--;
    	}

  2. #2
    Join Date
    Oct 2009
    Posts
    577

    Smile Re: Palindrome

    You have a string. Push all letters to a circular queue. Build a new string where you take the letters iterating from front. Build one more string where you take the letters from rear (if your queue has no iterators you may create 2 identical queues where you once pop the letters from front and second pop the letters from rear). Then compare the strings.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured