Thread: Implementing stack using class template

I've already checked the other two; apparently, they are unrelated.

The following program is designed to demonstrate class templates. The program will evaluate postfix expressions input to the console by pushing them in a stack, and then popping them and evaluating them as such, (ex. entering 3 4 + would equal 3+4 = 7).

The code is below. We are not to modify it, but to fill in the blanks, the places filled in indicated with two asterisks for a line, and one on each side for a part of a line. If I didn't know what to enter (if anything), I put three ?s. If you want to copy and compile for yourself, look for all the *s and ?s.

1) I'm turning up all sorts of errors in the main program file (prog5.cpp) having to do with stacktype.cpp. It has been removed from the program, as it is included at the end of stackType.h. Most of them are "cannot convert 'this' pointer from StackType to StackType<stack> &'. How do I fix that?

2) The program supposedly lacks a default constructor, and it keeps turning up that 's' is an array of unknown size (do I call StackType or stack or what?).

stackType.h

Code:

#pragma once//   Catherine Stringfellow and Trey Brumley
//	 A Stack is a data type, which stores values in an order where values are added to the top of the stack when pushed,
//   and when popped, remove and return the value from the top of the stack.


//   Class specification for Stack ADT in file StackType.h
using namespace std;


static const int MAXITEMS = 50;


template <class stack>**
class StackType
{
  public:
	// Class constructors
    StackType();
	StackType (const StackType & other);
    
    void makeEmpty();
    // Function:  Sets stack to an empty state.
    // Post: Stack is empty.


    bool isFull() const;
    // Function: Determines whether the stack is full.
    // Pre:  Stack has been initialized.
    // Post: Function value = (stack is full)


    bool isEmpty() const;
    // Function: Determines whether the stack is empty.
    // Pre:  Stack has been initialized.
    // Post: Function value = (stack is empty)


    void push(*stack&* item);
    // Function: Adds newItem to the top of the stack.
    // Pre:  Stack has been initialized.
    // Post: If (stack is full), PushOnFullStack exception is thrown;
    //       otherwise, newItem is at the top of the stack.


    void pop(*stack&* item);
    // Function: Removes top item from the stack and returns it in item.
    // Pre:  Stack has been initialized.
    // Post: If (stack is empty), PopOnEmptyStack exception is thrown;
    //       otherwise, top element has been removed from stack.
    //       item is a cop of the removed item.


	int getStackNum ();
	//Function: returns the number of items in the stack
	//Pre: Stack has been initialized
	//Post: Returns the number of items in the stack


private:
	int top;
    stack items[MAXITEMS];	//statically allocated array
};


#include "stacktype.cpp"

stacktype.cpp

Code:

using namespace std;

template <class stack>**
StackType*<stack>*::StackType()
{
  top = -1;  // I'm not to remove this, and it is turning up as a non-default constructor.
}


template<class stack>**
StackType*<stack>*::StackType (const StackType & other)
{
  top = other.top;
  for (int i=0; i < top; i++)
	  items[i] = other.items[i];
}


template<class stack>**
void StackType*<stack>*::makeEmpty()
{
  top = -1;
}


template<class stack>**
bool StackType*<stack>*::isEmpty() const
{
  return (top == -1);
}


template<class stack>**
bool StackType*<stack>*::isFull() const
{
  return (top == MAXITEMS-1);
}


template<class stack>**
void StackType*<stack>*::push(stack& newItem)
{
  if( !isFull() )
  {
    top++;
    items[top] = newItem;
  }
}


template<class stack>**
void StackType*<stack>*::pop(stack& item)
{
  if( !isEmpty() )
  {
    item = items[top];
    top--;
  }
}


template<class stack>**
int StackType*<stack>*::getStackNum ()
{
   return top+1;  
}

prog5.cpp

Code:

#include "stackType.h"#include <string>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <cctype>
using namespace std;


int getValidChoice ();
/* purpose: get valid option choice from menu
   prereq: NONE
   postcond: int (for a valid choice returned)
*/


void readString(string& s);
/* purpose: Reads a line into a string
   recieves: string <s>
   returns: NONE
*/
void printString(const string& s);
/* purpose: Prints a string
   recieves: const string <s>
   returns: NONE
*/
void convertPostfix(string& post, string& result);
/* purpose: converts a prefix expression to infix
   recieves: string <post>, string <result>
   returns: NONE
*/
void convert(StackType ??? & s, char ch);
/* purpose: pops two operands off a string stack and pushes the result
   recieves: string <post>, char <ch>
   returns: NONE
*/
void evalPostfix(string& post, double& answer);
/* purpose: calculates the value of the prefix expression
   recieves: string <post>, double <answer>
   returns: NONE
*/
void evaluate(StackType ??? & s, char ch);
/* purpose: pops two operands off a double stack and pushes the result
   recieves: Stack <s>, char <ch>
   returns: NONE
*/


void error(int m);
//prints an error message, based on int parametet


//print the introduction and exit screens
void intro();
void outro();


void main()
{					
	string post;
	double answer;
	int choice;


	//intro screen	
	intro();


	//while user wants to continue
	choice = getValidChoice();
	while (choice != 3) {
	
		//switch menu options
	   switch (choice)							
		{
		case 1:	
			cout<<"Please enter a postfix expression: ";
			readString(post);
			if (post == "")								//error if string empty 
				error(1);
			else
			{
				evalPostfix(post, answer);
				printString(post);
				cout<<" = "<<answer<< endl << endl;
			}
			break;
		
		case 2:
			cout<<"Please enter a postfix expression: ";
			readString(post);
			if (post == "")
				error(1);
			else
			{   string tempString = "";
				convertPostfix(post, tempString);
				cout<<"Postfix expression: ";
				printString(post);
				cout<<"\nEpression converted to infix: "<<tempString << endl<<endl;
			}
			break;
			default:	//if choice is not recognized print error
			  error(3);
	  } //end switch


	   choice = getValidChoice();
	} //end while
								
	outro();	


	//exit screen on return
	system("pause");
}


int getValidChoice ()
{														
	int choice;


	//display menu options
	cout<<" Options                               \n";
	cout<< "  (1) Evaluate postfix expression  " << endl;
	cout<< "  (2) Convert postfix to infix   " << endl;
	cout<< "  (3) Quit      " << endl;


	//get menu option
	cout<<"Enter option: ";
	cin>>choice;
	cout <<endl;


	//validate menu option
	while ((choice < 1) || (choice > 3)) {
		cout << "Enter a value between 1 and 3: ";
	    cin >> choice;
    }


	return choice;
}
		
void printString(const string& s)
{
	if (s.empty()) 
		cout<<"Empty";									//if string is empty print "empty"
	else
		cout<<s;
}


void readString(string& s)
{
	char temp[40];
	cin.ignore(80,'\n');								//clear buffer
	cin.getline(temp, 40);								//copy line to string
	s = temp;
}


void evalPostfix(string& post, double& answer)
{
	int index = 0, total = 0;					
	double tempDbl;
	bool negative = false;				//to detect negative signs
	*StackType* s;						//declare a stack of doubles 


	//loop index until end of string
	while (index < (int) post.length())						
	{
		//pass over spaces in string
		while (isspace(post[index]))					
			index++	;	


		//if operator evaluate incrementing index
		if (!isdigit(post[index]) && 
			!((index+1 < (int) post.length()) && 
			  (post[index] == '-' && isdigit(post[index+1]))))
		//if (!isdigit(post[index]))
			evaluate(s, post[index++]);					
		else
		{	//if number, checks for negative sign
			if (post[index] == '-')						
			{
				index++;
				negative = true;
			}


			//add up the digits from string
			while ((post[index] >= '0') && (post[index] <= '9'))
				total = (total * 10) + (post[index++] - '0');


			//if there was a negative sign, negate total
			if (negative)								
			{
				total = total * -1;
				negative = false;
			}


			//push number onto stack
			s.push(total);								
			total = 0;	
		}
								
		index++;
	}


	//pop answer from stack
	s.pop(tempDbl);										
	answer = tempDbl;


}


void evaluate(StackType ??? & s, char ch)
{
	double op1, op2;									


	//check if empty before popping operands
	if (!s.isEmpty())									
	{
		s.pop(op2);


		if (!s.isEmpty())
		{
			s.pop(op1);


			//push result
			switch(ch)									
			{
			case '+':
				s.push(op1 + op2);						
				break;
			case '-':
				s.push(op1 - op2);
				break;
			case '*':
				s.push(op1 * op2);
				break;
			case '/':
				s.push(op1 / op2);
				break;
			default:
				return;
			}
		}
	}
}


void convertPostfix(string& post, string& result)
{
	int index = 0;
	string tempString;
	StackType s;  //declare a stack of strings


	//loop index until end of string
	while (index < (int) post.length())						
	{
		//pass over spaces in string
		if (isspace(post[index]))						
			index++	;	


		//if operator convert incrementing index
		if (!isdigit(post[index]) && 
			!((index+1 < (int) post.length()) && 
			  (post[index] == '-' && isdigit(post[index+1]))))
		//if (!isdigit(post[index]))
			convert(s, post[index++]);					
		else
		{
			//clear string
			tempString.erase();							
		
			//concatenate numbers to string
			while (!isspace(post[index]))				
				tempString = tempString + post[index++];


			//push string onto stack
			s.push(tempString);							
		}
								
		index++;
	}
	//pop resulting string from stack
	s.pop(result);										
}


void convert(StackType ??? & s, char ch)
{
	string op1, op2, tempString;


	//check if empty before popping
	if (!s.isEmpty())									
	{
		s.pop(op2);


		if (!s.isEmpty())
		{
			s.pop(op1);


			//constructing string for result
			tempString = tempString + "( ";				
			tempString = tempString + op1;				


			//concatenate sign to string
			switch(ch)									
			{
			case '+':	
				tempString = tempString + " + ";		
				break;
			case '-':
				tempString = tempString + " - ";
				break;
			case '*':
				tempString = tempString + " * ";
				break;
			case '/':
				tempString = tempString + " / ";
				break;
			default:
				return;
			}


			//adding rest of the string
			tempString = tempString + op2;				
			tempString = tempString + " )";


			//push resulting string onto stack
			s.push(tempString);							
		}
	}
}


void error(int m)
{
	system("cls");			//clear screen
	cout<<"\a";				//system beep


	//displays error message according to parameter passed
	switch (m)											
	{
	case -1:
		cout<<"INTERNAL ERROR";
		break;
	case 1:
		cout<<"ERROR - Postfix expression empty.";
		break;
	case 3:
		cout<<"ERROR - invalid entry.";	
		break;
	default:
		cout <<"UNKNOWN ERROR.";
	}
	cout << endl << endl;
}


void intro()
{
	system("cls");										//clear screen
	//displays welcome message
	cout<<"Postfix Calculator and Converter\n\n";
}


void outro()
{
	cout<<"Goodbye...\n\n";								//display exit message
}

The asterisks are meant to indicate where I am able to fill in the blank. They're mostly intentional (there are some that are placed as pointers, but those should be obvious).

Changing all the <stack>s to <T>s hasn't really helped much. The declarations of the functions in the .h file with stack& as a parameter are turning up identifier errors. What will I use? stack was meant to be a template for a data type, used in the class.

Originally Posted by Trey Brumley

Changing all the <stack>s to <T>s hasn't really helped much. The declarations of the functions in the .h file with stack& as a parameter are turning up identifier errors. What will I use? stack was meant to be a template for a data type, used in the class.

And that's why it's not a good name -- it doesn't represent the stack itself, it represents the things inside the stack. As mentioned, T is traditional but if you don't like it you could perhaps use something like "item". But you need to change it everywhere -- there should not be any more "stack" in the code.

One thing I learned about templating that may or may not be relevant here is that it's totally okay to include a .cpp file which includes the .hpp file.

Oh man, then how am I supposed to write my code because I tried everything else and nothing worked as well as including .cpp files.