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
