jandhb
asked on
stack/queue
Can someone please show me how I would read a string of characters and push each character onto a stack and add them to a queue. Then use the basic stack and queue operations to determine if the string is a palindrome.
ASKER
I understand in theory what your saying, but I am new to this and need some help with the code. What you mind walking me through the functions that would make this happen, please. I appreciate it.
ASKER
BTW - I need to read the string from a text file. For example, in main right now I have...
int main()
{
string filename;
cout << "Enter filename: " << endl;
cin >> filename;
//Need size and filename for constructor
Stack sObject(1024,filename);
//convert a string object into a character array 'c_str()'
//Use variable name for file
ifstream fin(filename.c_str());
if (!fin)
{
std::cout << "Error: Unable to open " << filename << '\n';
return 1;
}
else
{
std::cout << "File opened" << '\n';
}
return 0;
}
How would I implement what you have said here...
for each character c in string {
push c on stack
enqueue c on queue
}
while not empty stack and not empty queue {
c1 = pop stack
c2 = dequeue queue
if c1 not equal c2 then string is not a palindrome
}
int main()
{
string filename;
cout << "Enter filename: " << endl;
cin >> filename;
//Need size and filename for constructor
Stack sObject(1024,filename);
//convert a string object into a character array 'c_str()'
//Use variable name for file
ifstream fin(filename.c_str());
if (!fin)
{
std::cout << "Error: Unable to open " << filename << '\n';
return 1;
}
else
{
std::cout << "File opened" << '\n';
}
return 0;
}
How would I implement what you have said here...
for each character c in string {
push c on stack
enqueue c on queue
}
while not empty stack and not empty queue {
c1 = pop stack
c2 = dequeue queue
if c1 not equal c2 then string is not a palindrome
}
What Language? Do you want a OO design, or a set of functions?
The basic algorithm would be something like this:
You use the stack to reverse the word, and use the Queue to keep the word in the same order.
1) Fill the stack and Queue with the same word:
s:We few
q:We few
2) While the Stack & Queue are not empty,
a) Remove an item from the stack
b) Remove an item from the Queue
c) Compare Item a) with Item b)
-If a) not equal b) then you DON'T have a palendrome. EXIT you are done
d) Repeat step #2 until stack and queue are emtpy
The basic algorithm would be something like this:
You use the stack to reverse the word, and use the Queue to keep the word in the same order.
1) Fill the stack and Queue with the same word:
s:We few
q:We few
2) While the Stack & Queue are not empty,
a) Remove an item from the stack
b) Remove an item from the Queue
c) Compare Item a) with Item b)
-If a) not equal b) then you DON'T have a palendrome. EXIT you are done
d) Repeat step #2 until stack and queue are emtpy
ASKER
I'm trying to learn C++ OO design, yes. Can you show me how this is done, please. I'm interested to learn.
ASKER
1. How do I fill the stack and Queue with the same word?
2. How do I do step 2?
2. How do I do step 2?
ASKER
Ok. Here is what I have so far...
It works when it is not a palindrome, but the debugger opens when the word actually is (for example, abcba). I dont think I have this...
if(Q_output[i]!=S_output[i ])
{
printf("\nThe words are not palindrome\n");
return 0;
}
else if(Q_output[i]==S_output[i ])
printf("\n%s",S_output[i]) ;
}
in main quite right???? What do I need to change?
-------------------------- ---------- ---------- --
main
#include "Stack.h"
#include "Queue.h"
main ()
{
Stack_t S;
Queue_t Q;
item_t input[SIZE],Q_output[SIZE] ="",S_outp ut[SIZE]=" ";
int i,length;
InitialiseStack(&S);
InitialiseQueue(&Q);
printf("Enter a words to reverse> ");
for(i=0,input[i]=getchar() ;input[i]! ='\n';i++, input[i]=g etchar())
{
insert(input[i],&Q);
push(input[i],&S);
}
length=strlen(input);
for(i=0;i<length;i++)
{
while(!emptystack(S)){
Remove(&Q,&Q_output[i]);
pop(&S,&S_output[i]);
}
if(Q_output[i]!=S_output[i ])
{
printf("\nThe words are not palindrome\n");
return 0;
}
else if(Q_output[i]==S_output[i ])
printf("\n%s",S_output[i]) ;
}
putchar('\n');
return 0;
}
-------------------------- ---------- ------
stack.h
#include <stdio.h>
#include <string.h>
#define SIZE 100
typedef char item_t;
typedef struct {
item_t Items[SIZE];
int top;
}Stack_t;
//------------------------ ---------- -------
void InitialiseStack (Stack_t *S)
{ S->top=0; }
int emptystack (Stack_t S)
{ return (S.top==0); }
int fullstack (Stack_t S)
{ return (S.top==SIZE); }
void push (char x,Stack_t *S)
{
if(fullstack(*S))
printf("stack overflow\n");
else{
S->Items[S->top]=x;
++(S->top);
}
}
void pop (Stack_t *S, char *x)
{
if(emptystack(*S))
printf("stack empty\n");
else{
--(S->top);
*x=S->Items[S->top];
}
}
-------------------------- ---------- ------
Queue.h
#include <stdio.h>
#include <string.h>
#define SIZE 100
typedef char item_t;
typedef struct{
int count,front, rear;
item_t Item[SIZE];
}Queue_t;
//------------------------ ---------- --------
void InitialiseQueue (Queue_t *Q)
{
Q->count=0;
Q->front=0;
Q->rear=-1;
}
int emptyq (Queue_t Q)
{ return (Q.count==0); }
int fullq (Queue_t Q)
{ return (Q.count==SIZE); }
void insert(item_t y, Queue_t *Q)
{
if (fullq(*Q))
printf("queue overflow\n");
else{
Q->rear=(Q->rear+1)%SIZE;
Q->Item[Q->rear]=y;
Q->count++;
}
}
void Remove (Queue_t *Q, item_t *y)
{
if(emptyq(*Q))
printf("queue empty\n");
else{
*y=Q->Item[Q->front];
Q->front=(Q->front+1)%SIZE ;
--(Q->count);
}
}
It works when it is not a palindrome, but the debugger opens when the word actually is (for example, abcba). I dont think I have this...
if(Q_output[i]!=S_output[i
{
printf("\nThe words are not palindrome\n");
return 0;
}
else if(Q_output[i]==S_output[i
printf("\n%s",S_output[i])
}
in main quite right???? What do I need to change?
--------------------------
main
#include "Stack.h"
#include "Queue.h"
main ()
{
Stack_t S;
Queue_t Q;
item_t input[SIZE],Q_output[SIZE]
int i,length;
InitialiseStack(&S);
InitialiseQueue(&Q);
printf("Enter a words to reverse> ");
for(i=0,input[i]=getchar()
{
insert(input[i],&Q);
push(input[i],&S);
}
length=strlen(input);
for(i=0;i<length;i++)
{
while(!emptystack(S)){
Remove(&Q,&Q_output[i]);
pop(&S,&S_output[i]);
}
if(Q_output[i]!=S_output[i
{
printf("\nThe words are not palindrome\n");
return 0;
}
else if(Q_output[i]==S_output[i
printf("\n%s",S_output[i])
}
putchar('\n');
return 0;
}
--------------------------
stack.h
#include <stdio.h>
#include <string.h>
#define SIZE 100
typedef char item_t;
typedef struct {
item_t Items[SIZE];
int top;
}Stack_t;
//------------------------
void InitialiseStack (Stack_t *S)
{ S->top=0; }
int emptystack (Stack_t S)
{ return (S.top==0); }
int fullstack (Stack_t S)
{ return (S.top==SIZE); }
void push (char x,Stack_t *S)
{
if(fullstack(*S))
printf("stack overflow\n");
else{
S->Items[S->top]=x;
++(S->top);
}
}
void pop (Stack_t *S, char *x)
{
if(emptystack(*S))
printf("stack empty\n");
else{
--(S->top);
*x=S->Items[S->top];
}
}
--------------------------
Queue.h
#include <stdio.h>
#include <string.h>
#define SIZE 100
typedef char item_t;
typedef struct{
int count,front, rear;
item_t Item[SIZE];
}Queue_t;
//------------------------
void InitialiseQueue (Queue_t *Q)
{
Q->count=0;
Q->front=0;
Q->rear=-1;
}
int emptyq (Queue_t Q)
{ return (Q.count==0); }
int fullq (Queue_t Q)
{ return (Q.count==SIZE); }
void insert(item_t y, Queue_t *Q)
{
if (fullq(*Q))
printf("queue overflow\n");
else{
Q->rear=(Q->rear+1)%SIZE;
Q->Item[Q->rear]=y;
Q->count++;
}
}
void Remove (Queue_t *Q, item_t *y)
{
if(emptyq(*Q))
printf("queue empty\n");
else{
*y=Q->Item[Q->front];
Q->front=(Q->front+1)%SIZE
--(Q->count);
}
}
The only thing remotely difficult with this assignment is the algorithm itself
which has been provided to you, including which stack and queue methods to use.
The only thing left is to implement the algorithm in your language of choice
It could be made even simpler if whatever standard library or toolkit you use
already provides Stack and Queue classes.
Experts are not allowed to actually do your assignment for you (we would learn
nothing and neither would you). This particular assignment is quite trivial (less
than 20 lines of code for the main algorithm) so we really cannot provide you
with the actual code.
which has been provided to you, including which stack and queue methods to use.
The only thing left is to implement the algorithm in your language of choice
It could be made even simpler if whatever standard library or toolkit you use
already provides Stack and Queue classes.
Experts are not allowed to actually do your assignment for you (we would learn
nothing and neither would you). This particular assignment is quite trivial (less
than 20 lines of code for the main algorithm) so we really cannot provide you
with the actual code.
ASKER
Brett,
I understand. With that said....
I have given you the code that I am currently working with. What I'm having problems with is that it will not display that it is a palindrome when in fact it is. It is displaying that it is not fine. Are you allowed to help me with this?
I understand. With that said....
I have given you the code that I am currently working with. What I'm having problems with is that it will not display that it is a palindrome when in fact it is. It is displaying that it is not fine. Are you allowed to help me with this?
ASKER
Ok. I changed a couple of things....
It is now displaying "It is a palindrome". However, it it displaying it for the length of the string. So, if the string is 5 letters it displays it 5 times...
for(i=0;i<length;i++)
{
while(!emptystack(S)){
Remove(&Q,&Q_output[i]);
pop(&S,&S_output[i]);
}
if(Q_output[i]!=S_output[i ])
{
printf("\nThe words are not palindrome\n");
return 0;
}
else
{
printf("It's a palindrome");
}
}
Should I move the else outside the for loop?
It is now displaying "It is a palindrome". However, it it displaying it for the length of the string. So, if the string is 5 letters it displays it 5 times...
for(i=0;i<length;i++)
{
while(!emptystack(S)){
Remove(&Q,&Q_output[i]);
pop(&S,&S_output[i]);
}
if(Q_output[i]!=S_output[i
{
printf("\nThe words are not palindrome\n");
return 0;
}
else
{
printf("It's a palindrome");
}
}
Should I move the else outside the for loop?
ASKER
Nevermind...
THank you for the help.
I put return 0 and it works fine.
THank you for the help.
I put return 0 and it works fine.
You should move the printf("It's a palindrome"); outside the loop
Oops, your code wasn't there when I started posting my last response.
Here are some comments:
1) You don't really need the input[SIZE],Q_output[SIZE] ="",S_outp ut[SIZE]=" ".
They are superfluous. The Stack and Queue objects hold all the state of the string
you need.
2) You don't need to call strlen(), as you can count the characters as you push them.
3) Since you know the length, and therefore how many items are in the stack and queue,
you don't need to check for BOTH the length AND stack is empty. Specifically, nested
loops are destroying your algorithm.
4) Be consistent with your method naming conventions (capitalization, model names, etc).
5)
Here are some comments:
1) You don't really need the input[SIZE],Q_output[SIZE]
They are superfluous. The Stack and Queue objects hold all the state of the string
you need.
2) You don't need to call strlen(), as you can count the characters as you push them.
3) Since you know the length, and therefore how many items are in the stack and queue,
you don't need to check for BOTH the length AND stack is empty. Specifically, nested
loops are destroying your algorithm.
4) Be consistent with your method naming conventions (capitalization, model names, etc).
5)
5) There is no 5.
But really, you have made things much more complicated than needed.
But really, you have made things much more complicated than needed.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
A quick question for you here. Currently, in main() I am hardcoding the words that I want to insert into the front and end functions. Can you tell me how I would read in a simple text file, say that looks like this...
sun
tree
apple
and have that be the data that gets inserted into the front and end. And then when I search I'm not hardcoding the word I am just looking through the file to see if its there. Does that make sense? Basically, I need to use this little txt file instead of me hard coding the words in. Here is what main() currently looks like.
-------------------------- ---------- ---------- ---------
#include "LinkedList.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main()
{
LinkedList list;
string word;
//insertFront
list.insertFront("Tree");
//insertEnd
list.insertEnd("Apple");
list.display();
//insertFront user input
cout << "Enter a word: " << endl;
cin >> word;
list.insertFront(word);
cout << "After user input list now contains: " << endl;
list.display();
//search
cout << "Search for: " << endl;
cin >> word;
if (list.search(word))
{
cout << "Already on list." << endl;
}
//list size
cout << "List size: " << list.getLength() << endl;
//return first value
//use the c_str() method to get a 'const char*' that cout can deal with
cout << "First value is: " << list.GetFirstValue().c_str () << std::endl;
//list.GetFirstValue();
//remove
list.remove("Tree");
cout << "After remove() is called list size is: " << list.getLength() << endl;
cout << "After remove(Tree) is called values in list are: " << endl;
list.display();
//remove first node
cout << "Remove First Node: " << endl;
list.RemoveFirstNode();
cout << "Items in list after removing first node: " << endl;
list.display();
//empty
cout << "Is the list empty: " << list.empty() << endl;
//deleteList
list.deleteList();
cout << "After deleteList() is called list size is: " << list.getLength() << endl;
return 0;
}
sun
tree
apple
and have that be the data that gets inserted into the front and end. And then when I search I'm not hardcoding the word I am just looking through the file to see if its there. Does that make sense? Basically, I need to use this little txt file instead of me hard coding the words in. Here is what main() currently looks like.
--------------------------
#include "LinkedList.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main()
{
LinkedList list;
string word;
//insertFront
list.insertFront("Tree");
//insertEnd
list.insertEnd("Apple");
list.display();
//insertFront user input
cout << "Enter a word: " << endl;
cin >> word;
list.insertFront(word);
cout << "After user input list now contains: " << endl;
list.display();
//search
cout << "Search for: " << endl;
cin >> word;
if (list.search(word))
{
cout << "Already on list." << endl;
}
//list size
cout << "List size: " << list.getLength() << endl;
//return first value
//use the c_str() method to get a 'const char*' that cout can deal with
cout << "First value is: " << list.GetFirstValue().c_str
//list.GetFirstValue();
//remove
list.remove("Tree");
cout << "After remove() is called list size is: " << list.getLength() << endl;
cout << "After remove(Tree) is called values in list are: " << endl;
list.display();
//remove first node
cout << "Remove First Node: " << endl;
list.RemoveFirstNode();
cout << "Items in list after removing first node: " << endl;
list.display();
//empty
cout << "Is the list empty: " << list.empty() << endl;
//deleteList
list.deleteList();
cout << "After deleteList() is called list size is: " << list.getLength() << endl;
return 0;
}
ASKER
how do I declare an array in my constructor to store the characters of a string...I'm using a queue.
Here is what I have so far.
Queue::Queue() : count(0), maxQSize(0), front(0), back(0)
{
queueArray[5];
}
My class....
class Queue
{
public:
Queue();
void enqueue(char);
bool full() const;
private:
char* queueArray;
int front;
int back;
int count;
int maxQSize;
};
#endif
Here is what I have so far.
Queue::Queue() : count(0), maxQSize(0), front(0), back(0)
{
queueArray[5];
}
My class....
class Queue
{
public:
Queue();
void enqueue(char);
bool full() const;
private:
char* queueArray;
int front;
int back;
int count;
int maxQSize;
};
#endif
A queue processes data like a bank or postal queue - First in, first out - First come, first served, etc
A queue processed like those spring-loaded plate stackers at the cafeteria - Last in, first out.
You iterate over a string, adding each of its characters to both the stack and the queue, until end of string.
The queue will now have the characters in the original order, whereas the stack will have the characters in reverse order.
By dequeuing a character from the queue and popping a character from the stack, you can compare the first character of the string to the last.
If the characters match as you pull them off the queue and the stack, then the string reads the same forward and backward (its a palindrome).
So the rough algorithm is this:
for each character c in string {
push c on stack
enqueue c on queue
}
while not empty stack and not empty queue {
c1 = pop stack
c2 = dequeue queue
if c1 not equal c2 then string is not a palindrome
}