Hey guys,

Can anyone tell me why this doesn't work in VS2008? I've commented out the #includes and whatnot so you can paste it into a single .cpp file and run it.

Here are my errors:

1>test.obj : error LNK2028: unresolved token (0A000320) "int __cdecl eval(class Tree<struct InfoNode> &)" (?eval@@$$FYAHAAV?$Tree@UInfoNode@@@@@Z) referenced in function "int __cdecl main(void)" (?main@@$$HYAHXZ)


1>test.obj : error LNK2028: unresolved token (0A00032D) "void __cdecl buildExprTree(class Tree<struct InfoNode> &)" (?buildExprTree@@$$FYAXAAV?$Tree@UInfoNode@@@@@Z) referenced in function "int __cdecl main(void)" (?main@@$$HYAHXZ)


1>test.obj : error LNK2019: unresolved external symbol "int __cdecl eval(class Tree<struct InfoNode> &)" (?eval@@$$FYAHAAV?$Tree@UInfoNode@@@@@Z) referenced in function "int __cdecl main(void)" (?main@@$$HYAHXZ)


1>test.obj : error LNK2019: unresolved external symbol "void __cdecl buildExprTree(class Tree<struct InfoNode> &)" (?buildExprTree@@$$FYAXAAV?$Tree@UInfoNode@@@@@Z) referenced in function "int __cdecl main(void)" (?main@@$$HYAHXZ)

And here's the code:

// queue.h
// linked list implementation of Queue ADT
#include <iostream>
#include <cstddef>		 	// for NULL
#include <new>				// for bad_alloc exception
using namespace std;

template <class T>
struct Node;					// forward reference, Node defined below

template<class T>
class Queue
{
  private:
	Node<T> * front;			// pointer to front of Queue
	Node<T> * rear;			// pointer to rear of Queue
	int length;				// logical length of Queue
  public:
  	Queue();			// default c-tor
	~Queue();			// d-tor

	void makeMT();		// make Queue logically empty
	// Post: front and rear have been reset to the empty state
	bool isMT() const;		// test for Queue being empty
					// returns true if the queue is empty; false otherwise
	bool isFull() const;	// test for Queue being full
					// Returns true if the queue is full; false otherwise
	void enqueue(T item);		// enqueue an item
	// Post: parameter item is at the rear of the queue
	void dequeue(T & item);	// dequeue an item
	// Post: front of queue has been removed and a copy returned in item
	int getLength() const;		// returns length queue  
	// Post: Queue is unchanged
	void replaceItem(T old, T nu);  // replaces all occurrences of old with nu
	// Pre:  queue has been initialized
	// Post:  each occurrence of old in queue has been changed to nu
	void prntQueue() const;	// displays contents of queue
	// Pre:  queue has been initialized
	// Post: contents of queue have been printed

}; // end Queue

	// implementations
/*template <class T>
struct Node 
{
    T info;
    Node<T> * next;
}; */

template<class T>			// default class c-tor
Queue<T>::Queue() : front(NULL), rear(NULL), length(0)			
{ }

template<class T>			// d-tor
Queue<T>::~Queue() 			
{
  makeMT();
}

template<class T>
void Queue<T>::makeMT()
{
	Node <T> * temp;

    while ( front != NULL )
    {
        temp = front;
        front = front->next;
        delete temp;
    } // endwhile
    rear = NULL;
	length = 0;
	return;
} // end makeMT()

template<class T>
bool Queue<T>::isMT() const
{
  return ( length == 0 );	// alternative is to return ( front == NULL );
} // end isMT()

template<class T>
bool Queue<T>::isFull() const
{
	Node<T> * location;
	try
	{
		location = new Node<T>;
		delete location;
		return false;
	} // endtry
	catch(bad_alloc exception)
	{
		return true;
	} // endcatch
} // end isFull()

template<class T>
void Queue<T>::enqueue(T item)
{
	Node<T> * newNode;

    newNode = new Node<T>;
    newNode->info = item;
    newNode->next = NULL;
    if ( rear == NULL )
        front = newNode;
    else
        rear->next = newNode;
    rear = newNode;
	length++;
} // end enqueue()

template<class T>
void Queue<T>::dequeue(T & item)
{ 
	Node<T> * temp;

    temp = front;
    item = front->info;
    front = front->next;
    if ( front == NULL )
        rear = NULL;
    delete temp;
	length--;
	return;
} // end dequeue()

template<class T>
int Queue<T>::getLength() const 
{
	return length;
} // end getLength()

template<class T>
void Queue<T>::replaceItem(T old, T nu) 
{
  Node<T> * location = front;
  
  while ( location != NULL )
  {
    if ( location->info == old )
        location->info = nu;
    location = location->next;
  } // endwhile
} // end replaceItem()

template<class T>
void Queue<T>::prntQueue() const
{
	Node<T> * location = front;
  
	cout << "\n Printing contents of queue:\n";
	while ( location != NULL )
	{
		cout << "\t" << location->info;
		location = location->next;
	} // endwhile
	cout << endl;
	return;
} // end prntQueue()
// end Queue implementations


// stack.h
// header file for Stack ADT using a templated linked list
//#pragma once

//#include "stkxcptn.h"
template <class T>
struct Node;	// forward reference - struct Node is defined below

template<class T>
class Stack
{
  private:
    Node<T> * top;

  public:
	Stack();
	~Stack();

    void makeMT();
    // 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 = false (assuming new succeeds)
 
    bool isMT() const;
    // Function:  determines whether the stack is empty
    // Pre:  Stack has been initialized
    // Post: Function value = (stack is empty)
  
    void push(T item);
    // Function:  adds item to the top of the stack
    // Pre:  Stack has been initialized
    // Post: If (stack is full), PushOnFullStack exception is thrown;
    //       otherwise, item is at the top of the stack
    
    void pop(T & item);
    // Function: removes top item from the stack and returns it in item
    // Pre:  Stack has been initialized 
    // Post: If (stack is MT), PopOnMTStack exception is thrown;
    //       otherwise, top element has been removed from stack

	void prntStack() const;
    // Function: displays contents of the stack  
    // Pre:  Stack has been initialized 
    // Post: Stack is walked and members printed
}; // end Stack

// stack.cpp

// Stack ADT - implementation using a templated linked list  

//#include <cstddef>
//#include <new>
template <class T>
struct Node
{
   T info;                                 //  Node data of type T
   Node * next;               				//  link to next Node

   Node<T>() : info(0), next(NULL)			// default c-tor for Node
   { }
		
   Node<T>( const T & e, Node * nx = NULL )  // parameterized c-tor for Node
		: info(e), next(nx) 
   { }
};  // end Node

template<class T>
Stack<T>::Stack() : top(NULL)
{ }

template <class T>
Stack<T>::~Stack()
{
  Node<T> * temp;
  
  while ( top != NULL )
  {
    temp = top;
    top = top->next;
    delete temp;
  } // endwhile
} // end ~Stack()

template<class T>
void Stack<T>::pop(T & item)
{
  if ( isMT() )
    throw PopOnMTStack();
  else
  {  
    Node<T> * temp;
    temp = top;
    item = top->info;
    top = top->next;
    delete temp;
  } // endif
} // end pop()

template<class T>
bool Stack<T>::isFull() const
{
  Node<T> * location;
  try
  {
    location = new Node<T>;
    delete location;
    return false;
  } // endtry
  catch(bad_alloc exception)
  {
    return true;
  } // endcatch
} // end isFull()

template <class T>
void Stack<T>::push(T item)
{
  if ( isFull() )
    throw PushOnFullStack();
  else
  {  
    Node<T> * ptr;
    ptr = new Node<T>(item);
    ptr->next = top;
    top = ptr;
  } // endif 
} // end push()

template <class T>
void Stack<T>::makeMT() 
{
  Node<T> * temp;
  
  while ( top != NULL )
  {
    temp = top;
    top = top->next;
    delete temp;
  } // endwhile
} // end makeMT()

template <class T>
bool Stack<T>::isMT() const
{
  return ( top == NULL );
} // end isMT()

template <class T>
void Stack<T>::prntStack() const
{
	Node<T> * ptr = top;
	cout << "\n Walking the stack:  "
	while ( ptr != NULL )
	{
		cout << "\t" << ptr->info;
		ptr = ptr->next;
	} // endwhile

  return;
} // end prntStack()

// stkxcptn.h - header file for PopOnMTStack and PushOnFullStack exception class

//#include <iostream>
//using namespace std;

class PopOnMTStack
{
  private :
	string msg;

  public :
	PopOnMTStack()  		// default c-tor
	{
		msg = string("\n Stack underflow - operation aborted");
	}
	const string message() const
	{
		return msg;
	}
}; // end PopOnMTStack


class PushOnFullStack
{
  private :
	string msg;

  public :
	PushOnFullStack()  		// default c-tor
	{
		msg = string("\n Stack overflow - operation aborted");
	}
	const string message() const
	{
		return msg;
	}
}; // end PopOnMTStack


// File Tree.h contains the definition of class Tree
// Class is templated

//#pragma once
//#include "Queue.h"
//#include "Stack.h"
#include <fstream>

const char LAST_SYMBOL = '=';
enum OpType { OPERATOR, OPERAND };

struct InfoNode
{
  OpType whichType; 	// Type field
  union 		// Anonymous union
  {
    char operation;
    int operand;
  };
};

typedef InfoNode T;

template <class T>
struct TreeNode;
// Assumption: T is a type for which the operators "<"
// and "==" are defined - either an appropriate built-in type or
// a class that overloads these operators

enum OrderType { PRE_ORDER, IN_ORDER, POST_ORDER };

template <class T>
class Tree
{
  private:
    TreeNode<T> * root;
    // The following queues are used for traversals
    Queue<T> preQue;
    Queue<T> inQue;
    Queue<T> postQue;
  public:
    Tree();			// constructor
    ~Tree();		// destructor
    Tree(const Tree<T> & oTree);
    // copy constructor
    void operator=(const Tree<T> & oTree);
    // Overloads the assignment operator
    void makeMT();
    // Function: Initializes tree to the empty state
    // Post: Tree is empty
    bool isMT() const;
    // Function: Determines whether the tree is empty
    // Post: Function value = (tree is empty)
    bool isFull() const;
    // Function: Determines whether the tree is full
    // Post: Function value = (tree is full)
    int numberOfNodes() const;
    // Function: Determines the number of elements in the tree
    // Post: Function value = number of elements in the tree
    void retrieveItem(T & item, bool & found);
    // Function: Retrieves item whose key matches item's key (if present)
    // Pre:  Key of item has been initialized
    // Post: If there is an item someItem whose key matches item's
    //       key, then found is true and item is a copy of someItem;
    //       otherwise found is false and item is unchanged
    //       The tree is unchanged
    void insertItem(T item);
    // Function: Adds item to the tree
    // Pre:  Tree is not full; item is not in the tree
    // Post: item is in the tree
    //       Binary search property is maintained
    void removeItem(T item);
    // Function: Deletes the item whose key matches item's key
    // Pre:  Key of item has been initialized
    //       One and only one item in the tree has a key matching
    //       item's key
    // Post: No element in tree has key matching item's key
    void resetTree(OrderType order);
    // Function: Initializes current position for an iteration
    //           through the tree in order specified
    // Post: Current position is prior to root of the tree
    void getNextItem (T & item, OrderType order, bool & fini);
    // Function: Gets the next element in the tree in the order specified in order
    // Pre:  Current position is defined
    //       Item at current position is not last in the tree
    // Post: Current position is one position beyond current position at entry to getNextItem()
    //       fini = (current position is last in tree)
    //       item is a copy of element at current position
    void printTree(std::ofstream & outFile) const;
    // Function: Prints the values in the tree in ascending key
    //           order on outFile
    // Pre:  outFile has been opened for writing
    // Post: Values in the three have been printed in ascending key order
    //       outFile is still open
	friend void buildExprTree(Tree<T> & expr);
	friend int eval(Tree<T> & expr);
}; // end Tree

//#include "Tree.cpp"

// Implementation file for Binary Search Tree; 
// recursive insertion and deletion functions


template <class T>
struct TreeNode
{
  T info;
  TreeNode * left;
  TreeNode * right;
  TreeNode() 			// default c-tor for TreeNode
  { }
};

template <class T>
int countNodes(Tree<T> * tree)
// Post: returns the number of nodes in the tree
{
  if (tree == NULL)
    return 0;
  else
    return countNodes(tree->left) + countNodes(tree->right) + 1;
}

template <class T>
int Tree<T>::numberOfNodes() const
// Calls recursive function CountNodes to count the
// nodes in the tree
{
  return countNodes(root);
}

template <class T>
void retrieve(TreeNode<T> * tree, T & item, bool & found)
// Recursively searches tree for item
// Post: If there is an element someItem whose key matches item's, found
//       is true and item is set to a copy of someItem; otherwise found
//       is false and item is unchanged
{
  if (tree == NULL)
    found = false;                          // item is not found
  else if ( item < tree->info )                 // Search left subtree
    retrieve(tree->left, item, found);      // Search right subtree
  else if ( item > tree->info )
    retrieve(tree->right, item, found);
  else
  {
    item = tree->info;                      // item is found
    found = true;
  }
}

template <class T>
void Tree<T>::retrieveItem(T& item, bool& found)
// Calls recursive function Retrieve to search the tree for item
{
  retrieve(root, item, found);
}

template <class T>
void insert(TreeNode<T> * & tree, T item)
// Inserts item into tree
// Post:  item is in tree; search property is maintained
{
  if ( tree == NULL )
  {							// insertion place found
      tree = new TreeNode<T>;
      tree->right = NULL;
      tree->left = NULL;
      tree->info = item;
  }
  else if ( item < tree->info )
    Insert(tree->left, item);      // insert in left subtree
  else
    Insert(tree->right, item);     // nsert in right subtree
}

template <class T>
void Tree<T>::insertItem(T item)
// Calls recursive function Insert to insert item into tree
{
  insert(root, item);
}

template <class T>
void removeNode(TreeNode<T> * & tree)
// Deletes the node pointed to by tree
// Post: The user's data in the node pointed to by tree is no longer in the
//       tree.  If tree is a leaf node or has only non-NULL child pointer
//       the node pointed to by tree is deleted; otherwise, the user's data
//       is replaced by its logical predecessor and the predecessor's node
//       is deleted
{
  T data;
  TreeNode<T>* tempPtr;
  
  tempPtr = tree;
  if ( tree->left == NULL )
  {
    tree = tree->right;
    delete tempPtr;
  }  
  else if ( tree->right == NULL )
  {
    tree = tree->left;
    delete tempPtr;
  }  
  else
  {
    getPredecessor(tree->left, data);
    tree->info = data;
    remove(tree->left, data);       // Delete predecessor node
  }
}

template <class T>
void remove(TreeNode<T>*& tree, T item)
// Deletes item from tree
// Post:  item is not in tree
{
  if (item < tree->info )
    remove(tree->left, item);         // Look in left subtree
  else if ( item > tree->info )
    remove(tree->right, item);        // Look in right subtree
  else
    removeNode(tree);                 // Node found; call removeNode
} 

template <class T>
void Tree<T>::removeItem(T item)
// Calls recursive function remove() to delete item from tree
{
  remove(root, item);
}

template<class T>
void getPredecessor(TreeNode<T> * tree, T & data)
// Sets data to the info member of the right-most node in tree
{
  while ( tree->right != NULL )
    tree = tree->right;
  data = tree->info;
}

template <class T>
void Tree<T>::printTree(std::ofstream & outFile) const
// Calls recursive function print() to print items in the tree
{
  print(root, outFile);
}

template<class T>
void print(TreeNode<T> * tree, std::ofstream & outFile)
// Prints info member of items in tree in sorted order on outFile
{
  if ( tree != NULL )
  {
    print(tree->left, outFile);             // Print left subtree
    outFile << tree->info;
    print(tree->right, outFile);            // Print right subtree
  }
}

template <class T>
Tree<T>::Tree()
{
  root = NULL;
}

template<class T>
void destroy(TreeNode<T> * & tree)
// Post: tree is empty; nodes have been deallocated
{
  if ( tree != NULL )
  {
    destroy(tree->left);
    destroy(tree->right);
    delete tree;
  }
}

template <class T>
Tree<T>::~Tree()
// Calls recursive function destroy() to destroy the tree
{
  destroy(root);
}

template <class T>
void copyTree(TreeNode<T> * & copy, TreeNode<T> * originalTree )
// Post: copy is the root of a tree that is a duplicate
//       of tree pointed to by originalTree
{
  if ( originalTree == NULL )
    copy = NULL;
  else
  {
    copy = new TreeNode<T>;
    copy->info = originalTree->info;
    copyTree(copy->left, originalTree->left);
    copyTree(copy->right, originalTree->right);
  }
}


template <class T>
Tree<T>::Tree(const Tree<T> & originalTree)
// Calls recursive function copyTree() to copy originalTree into root
{
  copyTree(root, originalTree.root);
}

template <class T>
void Tree<T>::operator=(const Tree<T> & originalTree)
// Calls recursive function CopyTree to copy originalTree into root
{
  if ( &originalTree == this )
    return;                       // Ignore assigning self to self
  destroy(root);                    // Deallocate existing tree nodes
  copyTree(root, originalTree.root);
}

// Function prototypes for auxiliary functions
template <class T>
void buildExprTree(Tree<T> & expr);
// builds a preorder binary expression tree

template <class T>
void preorder(TreeNode<T> *, Queue<T> &);
// Enqueues tree items in preorder

template <class T>
void inorder(TreeNode<T> *, Queue<T> &);
// Enqueues tree items in inorder

template <class T>
void postorder(TreeNode<T> *, Queue<T> &);
// Enqueues tree items in postorder

template <class T>
void Tree<T>::resetTree(OrderType order)
// Calls function to create a queue of the tree elements in
// the specified order
{
  switch ( order )
  {
    case PRE_ORDER : preorder(root, preQue);
		     break;
    case IN_ORDER  : inorder(root, inQue);
		     break;
    case POST_ORDER: postorder(root, postQue);
		     break;
  } // endswitch
}

template <class T>
void preorder(TreeNode<T> * tree, Queue<T> & preQue)
// Post: preQue contains the tree items in preorder
{
  if (tree != NULL)
  {
    preQue.enqueue(tree->info);
    preorder(tree->left, preQue);
    preorder(tree->right, preQue);
  }
}

template <class T>
void inorder(TreeNode<T>* tree, Queue<T>& inQue)
// Post: inQue contains the tree items in inorder
{
  if ( tree != NULL )
  {
    inorder(tree->left, inQue);
    inQue.enqueue(tree->info);
    inorder(tree->right, inQue);
  } // endif
}

template <class T>
void postorder(TreeNode<T> * tree, Queue<T> & postQue)
// Post: postQue contains the tree items in postorder
{
  if (tree != NULL)
  {
    postorder(tree->left, postQue);
    postorder(tree->right, postQue);
    postQue.enqueue(tree->info);
  } // endif
}

template <class T>
void Tree<T>::getNextItem(T & item, OrderType order, bool & fini)
// Returns the next item in the desired order
// Post: For the desired order, item is the next item in the queue
//       If item is the last one in the queue, fini is true; otherwise
//       fini is false
{
  fini = false;
  switch ( order )
  {
    case PRE_ORDER : preQue.dequeue(item);
					 if ( preQue.isMT() )
						fini = true;
					 break;
    case IN_ORDER  : inQue.dequeue(item);
					 if ( inQue.isMT() )
						fini = true;
					 break;
    case POST_ORDER: postQue.dequeue(item);
					 if ( postQue.isMT() )
						fini = true;
					 break;
  } // endswitched
}

template <class T>
void buildExprTree(Tree<T> & expr) 
{
	buildTree(expr.root);
} 

// buildTree.cpp
// buildTree() builds a binary expression tree.
// Note:  operands are restricted to single digits

//using namespace std;

void buildTree(TreeNode<T> * & tree)
{
  enum MoveType { RIGHT, LEFT };
  MoveType nextMove = LEFT;

  TreeNode<T> * nptr = new TreeNode<T>;
  TreeNode<T> * last;
  char symbol;

  Stack <TreeNode<T> *> stack;

  cin >> symbol;

  cout << " operator: " << symbol << endl;  // first symbol is an operator
  
  nptr->info.whichType = OPERATOR;
  nptr->info.operation = symbol;

  tree = nptr;

  cin >> symbol;			// this version uses single-digit operands
 
  while ( symbol != LAST_SYMBOL )
  {
    last = nptr;
    nptr = new TreeNode<T>;

    if ( ispunct(symbol) )
    {
      cout << " operator: " << symbol << endl;
      nptr->info.whichType = OPERATOR;
      nptr->info.operation = symbol;
    }
    else
    {
      cout << "  operand: " << symbol << endl;
      nptr->info.whichType = OPERAND;
      nptr->info.operand = int(symbol - '0');
      nptr->right = NULL;
      nptr->left = NULL;
    } // endif
    
    switch (nextMove)
    {
      case LEFT  :	last->left = nptr;
          			stack.push(last);
 					break;
      case RIGHT :	stack.pop(last);
         			last->right = nptr;
					break;
    } // endswitch
    
    if ( nptr->info.whichType == OPERATOR )
      nextMove = LEFT;
    else 
      nextMove = RIGHT;
    cin >> symbol;
  } // endwhile
  return;
} // end buildTree()


template <class T>
int eval(Tree<T> & expr) 
{
	return eval(expr.root);
} 

// Function to evaluate a binary expression tree.
// Pre:   ptr is a pointer to a binary expression tree
// Post:  Function value = the value of the expression
//		  represented by the binary tree pointed to by ptr
int eval(TreeNode<T> * ptr)
{     
	switch ( ptr->info.whichType ) {        				
		case OPERAND :  
			return  ptr->info.operand;
		case OPERATOR :
			switch ( ptr->info.operation ) {
				case  '+' :  return ( eval(ptr->left) + eval(ptr->right) ); 

				case  '-' :  return ( eval(ptr->left) - eval(ptr->right) );

 				case  '*' :  return ( eval(ptr->left) * eval(ptr->right) ); 
					
				case  '/' :  return ( eval(ptr->left) / eval(ptr->right) );

             } // endswitch
       } // endswitch
} // end eval()

//tstexpr.cpp
/* ------------------------------------------------------------------------------
 * program to test binary tree expression evaluation
 * 	CS 320 - Data Structures 	l l craddock		   
 */

//#include "tree.h"

void main()
 {
	Tree<T> e ;  

	cout << "\n Use a Binary Tree for Preorder Expression Evaluation\n" ;

	cout << "\n Enter an expression terminated by an equal sign, e.g.:  - * 6 3 5 =\n" ;

	buildExprTree(e) ;

	cout << "\n The value of the expression is " << eval(e) ;

	cout << "\n -- Done --\n" ;
	return ;
 } 

/* Sample output:

 Use a Binary Tree for Preorder Expression Evaluation

 Enter an expression terminated by an equal sign, e.g.:  - * 6 3 5 =
*  -  8 5  /  +  4 2 3 =
 operator: *
 operator: -
  operand: 8
  operand: 5
 operator: /
 operator: +
  operand: 4
  operand: 2
  operand: 3

 The value of the expression is 6
 -- Done --                            */

Please help! I'm almost positive it was working at one point in vs2008 but now it doesn't seem to work in anything other than VS6.0

I think the two friend declarations need template <class T>

template <class T>
class Tree
{
...
template <class T> friend void buildExprTree(Tree<T> & expr);
template <class T> friend int eval(Tree<T> & expr);
...
};

Near miss.......

template <class T>
class Tree
{
...
template <typename T> friend void buildExprTree(Tree<T> & expr);
template <typename T> friend int eval(Tree<T> & expr);
...
};
This question has already been answered. Start a new discussion instead.