-
December 7th, 2010, 09:45 AM
#1
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--;
}
-
December 7th, 2010, 10:27 AM
#2
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|