Queue Stack Palindrome

Hello everyone, I've recently learned about queues and fully understand that they follow a fifo order as opposed to stacks that follow a filo order. I am now trying to write a program that will check a word entered in a queue and a stack to see if the are both the same forwards and backwards. I began writing the program and testing it as I went along but am having problems. I was going to complete the main part of the program but kept receiving 3 error messages. I've included the .cpp file below and will include the stack/header file in a quick reply. Does anyone have any suggestions? I wanted to get this part working with a user input just so I could go on to the next step and have it read from a document and write to another one (infile, ios::..., outfile...). This has been driving me crazy but I've managed to complete most of it thanks to all of your help with my previous problem (Reverse output (stack)).

Please let me know if you have any suggestions

*Error Message

--------------------Configuration: palindrome3 - Win32 Debug--------------------
Compiling...
palindrome3.cpp
c:\documents and settings\steve\desktop\palindrome\palindrome3.h(8) : error C2146: syntax error : missing ';' before identifier 'Stack'
c:\documents and settings\steve\desktop\palindrome\palindrome3.h(8) : error C2501: 'Class' : missing storage-class or type specifiers
c:\documents and settings\steve\desktop\palindrome\palindrome3.h(8) : fatal error C1004: unexpected end of file found
Error executing cl.exe.

palindrome3.obj - 3 error(s), 0 warning(s)

Code:

# include "palindrome3.h"
# include <iostream.h>

void blankspace(char *s, char *t)

{while (*s!=NULL)

{if (*s!=' ')

*t=*s;t++

s++;

}

*t=NULL; //append NULL to newstring

}

 

void main ()

{const int True=1, False=0;

// create stack object to store string in reverse order.

Stack S;

char palstring[ 80] , blankspacestring[ 80] , c;

int i=0; // string pointer

int ispalindrome=True; //we'll stop if false

// get input

cin. Getline(palstring,80,'\n');

//remove blanks

blankspace(palstring,blankspacestring);// A[],the array;A pointer to A[]

//push character onto stack

i=0;

while(blankedspacestring[i] !=NULL)

{

S.Push(blankspacestring[i] );

i++;

}

//now pop one-by-one comparing with original

i=0;

while (!S.StackEmpty())

{

c=S.Pop();

//get out of loop when first nonmatch

if (c!=blankspacestring[i])

{isPalindrome=False;

break;

}

// continue till end of string

i++;

}

//operation finished. Printout result

if (ispalindrome)

cout<<"\"<<palstring<<"\"<<"is a palindrome<<endl;

else

cout<<"\"<<palstring<<"\"<<"is not a palindrome<<endl;

This is the header file

Code:

# include <iostream.h>
# include <stdlib.h>

const int MaxStackSize=50;

Class Stack

{

private:

DataType stacklist[ MaxStackSize] ;

int top;

public:

Stack(void); // constructor, initialize top

//modification operations

void Push(const DataType& item);//same as void Push(DataType item)

DataType Pop(void);

void ClearStack(void);

//just copy top item without modifying stack contents

DataType Pick(void) const;

//check stack state

int StackEmpty(void) const;

int StackFull(void) const;

}

// Stack implementation

Stack::Stack(void):top(-1)

{}

//Push

void Stack::Push(const DataType& item)

{

//can not push if stack has exceeded its limits

if (top==MaxStackSize-1)

{

cerr<<"Stack overflow"<<endl;

exit(1);

}

// increment top ptr and copy item into list

top++;

stacklist[ top] =item;

}

//pop

DataTaype Stack::Pop(void)

{

DataType temp;

// if stack is empty nothing to pop

if (top==-1)

{ cerr<<"Stack empty"<<endl;

exit(1);

}

//record the top element

temp=stacklist[ top] ;

//decrement top and return the earlier top element

top--;

return temp;

}

//Peek is the same as Pop, except top is not moved

DataType Stack::Peek(void) const

{

}

//Stack Empty

int stack:.StackEmpty(void) const

{

return top==-1; //value is 1 if equal, 0 otherwise

}

// Stack Full

int Satck::StackFull(void) const

{

return top==MaxstackSize-1;

}

//Clear Stack

void Stack::ClearStack(void)

{

top=-1;

}
};

int stack:.StackEmpty(void) const <- this might be a problem
i don't get the 'datatype' thing, i don't see any templates, the bane of my soul. is this a new addition to the language? if no, replace your DataType with a real type.

plus, a little less whitespace please. i don't know if it's intentional or because of the paste, but it would look a lot nicer in a compact form (for instance, it would fit on one screen and i could read it)

e: oh boy my eyes are broken on top of everything else

>Class Stack
C++ is case sensitive, and all keywords are lower case. You want:

Code:

class Stack

Looking though your code there were several gramatical errors, they were pretty easy to miss since the way the code is layed out its hard to see what belongs where. I added a few comments where i found the missing pieces as I was conforming the code to be more readable.

Also i dont know what compiler your useing but i get a slew of ISO errors compileing it. after I delcared a data type wich is also missing in there.

main.cpp

Code:

# include "palindrome3.h"
# include <iostream.h>

void blankspace(char *s, char *t)
{
    while (*s!=NULL)
        {
        if (*s!=' ') *t=*s;
        t++; //missing ; here
        s++;
        }
*t=NULL; //append NULL to newstring
}
 

int main(void) //void main() bad
{
    const int True=1, False=0;
// create stack object to store string in reverse order.
    Stack S;
char palstring[ 80] , blankspacestring[ 80] , c;
int i=0; // string pointer
int ispalindrome=True; //we'll stop if false

// get input
cin. Getline(palstring,80,'\n');

//remove blanks
blankspace(palstring,blankspacestring);// A[],the array;A pointer to A[]

//push character onto stack
i=0;
while(blankedspacestring[i] !=NULL)
{
    S.Push(blankspacestring[i] );
    i++;
}

//now pop one-by-one comparing with original

i=0;
while (!S.StackEmpty())
{
    c=S.Pop();
//get out of loop when first nonmatch
    if (c!=blankspacestring[i])
         { 
          isPalindrome=False;
          break;
          }
 // continue till end of string
    i++;
}

//operation finished. Printout result
if (ispalindrome) cout<<"\"<<palstring<<"\"<<"is a palindrome<<endl;
 else cout<<"\"<<palstring<<"\"<<"is not a palindrome<<endl;
 
return(0); //missing a return and the final }
}

header

Code:

# include <iostream.h>
# include <stdlib.h>

const int MaxStackSize=50;

class Stack
{

private:
DataType stacklist[ MaxStackSize] ;
int top;

public:
Stack(void); // constructor, initialize top

//modification operations
void Push(const DataType& item);//same as void Push(DataType item)
DataType Pop(void);
void ClearStack(void);

//just copy top item without modifying stack contents
DataType Pick(void) const;

//check stack state
int StackEmpty(void) const;
int StackFull(void) const;
}

// Stack implementation
Stack::Stack(void):top(-1)
{/*void stack function to be filled in later? */} 

//Push
void Stack::Push(const DataType& item)
{
//can not push if stack has exceeded its limits
    if (top==MaxStackSize-1)
    {
    cerr<<"Stack overflow"<<endl;
    exit(1);
    }
// increment top ptr and copy item into list
top++;
stacklist[ top] = item;
}

//pop
DataTaype Stack::Pop(void)
{
    DataType temp;
    // if stack is empty nothing to pop
    if (top==-1)
    { 
    cerr<<"Stack empty"<<endl;
    exit(1);
    }
//record the top element
temp=stacklist[ top] ;
//decrement top and return the earlier top element
top--;
return temp;
}

//Peek is the same as Pop, except top is not moved
DataType Stack::Peek(void) const
{

}

//Stack Empty
int stack:.StackEmpty(void) const
{
    return top==-1; //value is 1 if equal, 0 otherwise
}

// Stack Full
int Satck::StackFull(void) const
{
    return top==MaxstackSize-1;
}

//Clear Stack
void Stack::ClearStack(void)
{
    top=-1;
}

//some extra chrs down here not attached to function. Also there is no
//define function. while only included once in your project you
//should probley get used to adding it to prevent multiple defnitions
//in larger projects.

Hi everyone, thanks...I've gotten the program to work properly. Once question I have now is...I now am trying to import the words from a text file and have the program read them and then export the answer (**** is a palindrome, not a palindrome) to a text file. Im just trying this part on my own (for extra credit) and because I was told that it wasn't that difficult. I have an idea of how to do it using ios::, but that's about all I do know. My guess is that it will definitely have to go in the main but I am definitely clueless as far as what else has to go with this. Please let me know if you have any suggestions

Thanks in advance

Please let me know if you need a working sample of my code

You read from a file by including <fstream> and creating an object of the type ifstream. You write to a file by creating an object of type ofstream. Then just use them like cin and cout:

Code:

#include <cstdlib> // For EXIT_FAILURE and EXIT_SUCCESS
#include <fstream>
#include <iostream>
#include <string>

using namespace std;

int
main()
{
  string   s;
  ifstream in("somefile");

  if (!in) { // Check for success
    cerr<<"Couldn't open file for reading"<<endl;
    return EXIT_FAILURE;
  }
  getline(in, s);
  cout<< s <<endl;
  ofstream out("someotherfile");
  if (!out) { // Check for success
    cerr<<"Couldn't open file for writing"<<endl;
    return EXIT_FAILURE;
  }
  out<<"Writing to a file!"<<endl;

  return EXIT_SUCCESS;
}

Hi this is my completed code which was working. I placed the ifstream line in my code which successfully reads my (palindromeinput.txt) but it gives me a strange output so I stopped at that point. In my text file I have
anna
johnson

My output is
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠ ╠╠Error Queue is full
Error Queue is full
Stack is full.
Error Queue is full
Stack is full.
Error Queue is full
is a palindrome
Press any key to continue

I wanted to get it working correctly before I have the output go to a text file (palindromeoutput).
I stopped at the //////////point. If i remove the fsream objects the program will work with user input but I cannot get it to work correctly with fstream/with what I've written so far. Please let me know if you have any suggestions.

Thanks in advance

Code:

#include<iostream>
#include <cstdlib> // For EXIT_FAILURE and EXIT_SUCCESS
#include <fstream>
#include<string>
using namespace std;
const int MAX=50;    // initialize max string size of 50 characters
typedef char StackElement;  // define StackElement
typedef char QueueElement;  // define QueueElement
class Stack
{
public:
	Stack(){top=-1;arr[MAX]=0;}   // default stack constructor
		void push(StackElement & ch);  // push function
		StackElement topNpop();         // top and pop functions combined
		bool empty() const;            // empty function
private:
		StackElement arr[MAX];    // define char array
		int	top;                  // define int top
	
};
/*******************************************
FUNCTION: push()
DESCRIPTION: Pushes an element onto the stack
PRECONDITION: Waiting for function call
POSTCONTION: New element character on top of stack
*******************************************/
inline void Stack::push(StackElement & ch)
{
	if(top<MAX)
	{
		top++;          // increment top
		arr[top]=ch;  // push onto stack
	}
	else
	{
		cout<<"Stack is full.\n";  // display stack is full
	}


}
/*******************************************
FUNCTION: topNpop()
DESCRIPTION: Reads and pops top element off the stack
PRECONDIION: Waiting for function call
POSTCONDITION:  One element read and removed fromt he stack
RETURN: Top element from stack
********************************************/

inline StackElement Stack::topNpop()
{
	if(top>-1)
	{
		return(arr[top]);  // returns top element
		top--;				// remove froms stack
	}
	else
	{
		cout<<"Stack is empty.\n";  // display stack is empty
		return(0);

	}

}
/*******************************************
FUNCTION: empty()
DESCRIPTION: returns result value if stack is empty
PRECONDITION: result=false
POSTCONDITION: result may be true or remain false
RETURN: result if true or false
********************************************/			
inline bool Stack::empty() const
{
	bool result=false;   // initialize bool as false
	if (top==-1)         
	{
		result=true;        // if top is -1 return result true
		return(result);
	}
	else
	{
		return(result);     // else return false
	}
}
class Queue                           // Queue class
{
public:
		Queue(){front=0, back=0;arr[MAX]=0;}   // Queue default constructor
		void addq(QueueElement & ch);          // define addq 
		QueueElement frontNremoveq();         // define frontNremove
private:
		QueueElement arr[MAX];            // initialize QueueElement array
		int front, back;                  // initialize int front and back
	
};
/*******************************************
FUNCTION: addq()
DESCRIPTION: adds an element onto the queue
PRECONDITION: Waiting for element to add
POSTCONDITION: New element now on the queue
********************************************/
inline void Queue::addq(QueueElement &ch)
{
	if(front!=(back+1)%MAX)
	{
		arr[back]=ch;     // add element to back of queue
		back=(back+1)%MAX;
	}
	else
	{
		cerr<<"Error Queue is full\n";  // display queue is full
	}
}
/*******************************************
FUNCTION: frontNremoveq()
DESCRIPTION: reads and removes front element from queue
PRECONDITION: front pointing to front of queue
POSTCONDITION: front element is returned and then incremented
********************************************/
inline QueueElement Queue::frontNremoveq()
{
	if(front!=back)
	{
		return(arr[front]);    // return front element
		front++;				// remove front element
	}
	else
	{
		cout<<"Queue is empty.\n";  // display queue is empty
		return(0);
	}
}

/***************************MAIN******************************/
int main()
{
	Stack S;	// initialize stack
	Queue Q;	// initialize queue
	int i=0;	// initialze int 'i'
	char string[MAX];  // initialize char string
	bool RESULT=false;  // initilize bool RESULT to false
	
	 ifstream in("palindromeinput.txt");
	if (!in) { // Check for success
    cerr<<"Couldn't open file for reading"<<endl;
    return EXIT_FAILURE;
	}
////////////////////////////////////////////////////////////////////////////
	cout<<string;				// output string
	while(string[i]!=NULL)
	{
		S.push(string[i]);  // push chars individually from string to
		Q.addq(string[i]);		// stack and queue
		i++;      // next char
	}
	while(i>0)
	{
		if(S.topNpop()==Q.frontNremoveq())  // compare each element from
		{										// stack and queue
			RESULT=true;  // if same for all chars return true
		}
		else
		{
			RESULT=false;  // if not same for any char break and return false
			break;
		}
		i--;
	}	
	if(RESULT==true)
	{
		cout<<" is a palindrome\n";  // display if true
	}
	else
	{
		cout<<" is not a palindrome\n"; // display if false
	}
	
	return 0;  // end of program
}

Um...you don't take any input from the file. Your input buffer is uninitialized, so your logic won't work too well and accessing it is undefined behavior. You should try again, this time walking through the exact steps that you need to perform to solve the problem. Do this on paper so that you aren't distracted by the computer. The basic idea is this:

1) Read a string from the file
2) If the string isn't empty push each character onto the stack/queue. If the string is empty, terminate.
3) Pop each character off the stack/queue and test it for equality until both the stack and queue are empty. Print the result.
4) Go to step 1

Hi everyone, I've gotten up to this point but am still having problems. I now have it so that the program is reading from the text file successfully but I cannot get it to successfully write to the output file. Also I believe that it is not checking correctly for palindrome but I am more worried about getting it to write to the output file. Am I missing something small

Thanks

Code:

#include<iostream>
#include <cstdlib> // For EXIT_FAILURE and EXIT_SUCCESS
#include <fstream>
#include<string>
using namespace std;
const int MAX=50;    // initialize max string size of 50 characters
typedef char StackElement;  // define StackElement
typedef char QueueElement;  // define QueueElement
class Stack
{
public:
	Stack(){top=-1;arr[MAX]=0;}   // default stack constructor
		void push(StackElement & ch);  // push function
		StackElement topNpop();         // top and pop functions combined
		bool empty() const;            // empty function
private:
		StackElement arr[MAX];    // define char array
		int	top;                  // define int top
	
};
/*******************************************
FUNCTION: push()
DESCRIPTION: Pushes an element onto the stack
PRECONDITION: Waiting for function call
POSTCONTION: New element character on top of stack
*******************************************/
inline void Stack::push(StackElement & ch)
{
	if(top<MAX)
	{
		top++;          // increment top
		arr[top]=ch;  // push onto stack
	}
	else
	{
		cout<<"Stack is full.\n";  // display stack is full
	}


}
/*******************************************
FUNCTION: topNpop()
DESCRIPTION: Reads and pops top element off the stack
PRECONDIION: Waiting for function call
POSTCONDITION:  One element read and removed fromt he stack
RETURN: Top element from stack
********************************************/

inline StackElement Stack::topNpop()
{
	if(top>-1)
	{
		return(arr[top]);  // returns top element
		top--;				// remove froms stack
	}
	else
	{
		cout<<"Stack is empty.\n";  // display stack is empty
		return(0);

	}

}
/*******************************************
FUNCTION: empty()
DESCRIPTION: returns result value if stack is empty
PRECONDITION: result=false
POSTCONDITION: result may be true or remain false
RETURN: result if true or false
********************************************/			
inline bool Stack::empty() const
{
	bool result=false;   // initialize bool as false
	if (top==-1)         
	{
		result=true;        // if top is -1 return result true
		return(result);
	}
	else
	{
		return(result);     // else return false
	}
}
class Queue                           // Queue class
{
public:
		Queue(){front=0, back=0;arr[MAX]=0;}   // Queue default constructor
		void addq(QueueElement & ch);          // define addq 
		QueueElement frontNremoveq();         // define frontNremove
private:
		QueueElement arr[MAX];            // initialize QueueElement array
		int front, back;                  // initialize int front and back
	
};
/*******************************************
FUNCTION: addq()
DESCRIPTION: adds an element onto the queue
PRECONDITION: Waiting for element to add
POSTCONDITION: New element now on the queue
********************************************/
inline void Queue::addq(QueueElement &ch)
{
	if(front!=(back+1)%MAX)
	{
		arr[back]=ch;     // add element to back of queue
		back=(back+1)%MAX;
	}
	else
	{
		cerr<<"Error Queue is full\n";  // display queue is full
	}
}
/*******************************************
FUNCTION: frontNremoveq()
DESCRIPTION: reads and removes front element from queue
PRECONDITION: front pointing to front of queue
POSTCONDITION: front element is returned and then incremented
********************************************/
inline QueueElement Queue::frontNremoveq()
{
	if(front!=back)
	{
		return(arr[front]);    // return front element
		front++;				// remove front element
	}
	else
	{
		cout<<"Queue is empty.\n";  // display queue is empty
		return(0);
	}
}

/***************************MAIN******************************/
int main()
{
	Stack S;	// initialize stack
	Queue Q;	// initialize queue
string s;
	int i=0;	// initialze int 'i'
	char string[MAX];  // initialize char string
	bool RESULT=false;  // initilize bool RESULT to false
	

  
ifstream inside ("palindromeinput.txt");
  if (! inside.is_open())
  { cout << "Error opening file"; exit (1); }

  while (! inside.eof() )
  {
    inside.getline (string,100);
    cout << string << endl;
  }

while(string[i]!=NULL)
	{
		S.push(string[i]);  // push chars individually from string to
		Q.addq(string[i]);		// stack and queue
		i++;      // next char
	}
	while(i>0)
	{
		if(S.topNpop()==Q.frontNremoveq())  // compare each element from
		{										// stack and queue
			RESULT=true;  // if same for all chars return true
		}
		else
		{
			RESULT=false;  // if not same for any char break and return false
			break;
		}
		i--;
	}	


if(RESULT==true)
	{
		cout<<string<<" is a palindrome\n";  // display if true
	}
	else
	{
		cout<<string<<" is not a palindrome\n"; // display if false
	}
	


ofstream outside ("palindromeoutput.txt");
  if (outside.is_open())
  {
  
	 outside << string;
    outside<< string;
    outside.close();
  }
  return 0;
}

What are you trying to write to the output file? It looks like right now you are just ending up writing the same string twice to the file. Is it supposed to be outputting all the palindrome matches to the file?

Is the purpose of this program to test your Stack and Queue classes in the setting of a palindrome problem or simply to test a palindrome program using a stack and queue data structures? You might have started off this program by implementing the solution using the built in STL stack and queue templates and when that was working, you could switch over to using your own Stack and Queue classes to see if your implementation worked. So, would you be averse to trying this with the built ins and seeing if it works, or are you confident that your implementation is correct. That would narrow your likely problem down to either your classes, or the logic/flow of the code in your main function.

If you just want a program to tell if a string is a palindrome or not, the code to loop through the file, read in a string and output that same string along with a basic "yes it is" or "no it isn't" can be done in about a half dozen lines of code.

Hi, I wanted the program to look at the input file (palindromeinput.txt) and read the data inside (DAD). It is then supposed to compare (stack/queue) and check to see if it is a palindrome. Once this check is complete it is supposed to write the result to the output file (palindromeoutput.txt) and state

DAD is a palindrome

I wanted to use a few entries but wanted to first get it working with just the DAD entry

I wanted the program to look at the input file (palindromeinput.txt) and read the data inside (DAD). It is then supposed to compare (stack/queue) and check to see if it is a palindrome. Once this check is complete it is supposed to write the result to the output file (palindromeoutput.txt) and state

DAD is a palindrome

Compare your setup with the following. The principle is the same even though I use the standard stack and queue interfaces rather than hand rolled classes.

Code:

#include <cstdlib>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <string>

using namespace std;

bool is_pal(const string& s);

int main()
{
  string   line;
  ifstream in("input.txt");

  if (!in) {
    cerr<<"Unable to open input file"<<endl;
    return EXIT_FAILURE;
  }
  while (getline(in, line)) {
    if (is_pal(line)) {
      cout<< line <<" is a palindrome"<<endl;
    }
    else {
      cout<< line <<" is not a palindrome"<<endl;
    }
  }

  return EXIT_SUCCESS;
}

namespace {
  template <typename T>
  T push_string(const string& s)
  {
    T                      ret;
    string::const_iterator it = s.begin();

    while (it != s.end()) {
      ret.push(*it);
      ++it;
    }

    return ret;
  }
}

bool is_pal(const string& s)
{
  queue<char> qu = push_string< queue<char> >(s);
  stack<char> st = push_string< stack<char> >(s);

  while (!qu.empty()) {
    if (qu.front() != st.top()) {
      return false;
    }
    qu.pop();
    st.pop();
  }

  return true;
}

It all should be pretty straightforward except for maybe the push_string template. The code for make_stack and make_queue would be virtually identical except for the types, and that's what templates were made for. The template does require a specific interface for type T though, specifically, it has to support the push operation using characters as the argument. For a generic function that would be unwise due to safety, but for this simple use, it's okay.

Hi RobC thanks for all of your help. I understand that part now but how can I take the output and place it into my output file (palindromeoutput.txt) . I thought I had it correctly in my setup but it will not work.

Thanks in advance

>but how can I take the output and place it into my output file
It takes only a minor change to write to file instead of standard output:

Code:

int main()
{
  string   line;
  ifstream in("input.txt");
  ofstream out("output.txt");

  if (!in) {
    cerr<<"Unable to open input file"<<endl;
    return EXIT_FAILURE;
  }
  if (!out) {
    cerr<<"Unable to open output file"<<endl;
    return EXIT_FAILURE;
  }
  while (getline(in, line)) {
    if (is_pal(line)) {
      out<< line <<" is a palindrome"<<endl;
    }
    else {
      out<< line <<" is not a palindrome"<<endl;
    }
  }

  return EXIT_SUCCESS;
}