Data Structures Exercises

1.Modify the program eval.cpp , which calculates the value of an arithmetic expression, to also accept variable identifiers in the expressions. The first time an identifier is encountered in the expression, the program should ask the user for the value of this variable and store it in a map. For every further appearance of an identifier that is already stored in the map the program should use the stored value.

2.Change the implementation of the binary search tree (cpp and header file attached ) in the following way: In the TreeNode class add a pointer to the parent node in the tree. Modify the insert and erase functions to properly set those pointers to parent nodes. Then define a TreeIterator class that contains a pointer to a TreeNode. The trees begin member function returns an iterator that points to the leftmost leaf. The iterators get member function returns the data value of the node to which it points. Its next member function needs to find the next element in inorder traversal in the following way:

• If the current node has a right child, then go to the leftmost child of the right child;
• Otherwise keep moving up to the parent until your current node is a left child. Move one step up to the parent of this node.

Make a main program to test your new implementation of a binary search tree and its iterator. Suggested extension: also overload appropriate operators to use with iterators.

3.Implement a template class Set that stores a finite set of elements. Implement the set with a binary search tree. Supply add and remove member functions to add and remove set elements. Overload the following operators:

| for set union
& for set intersection
- for set difference
<< to send the set content to a stream

Test with integers, strings, and at least one user-defined class. For the test with integers use random number generation in a range in a loop.

Hint: First implement the class for some fixed data type, for example integers or strings, and then convert it to a template class. It makes sense to submit both the non-template and the template implementations.

Problem 4 Implement an associative array that uses strings for keys and stores values of type double. Use hashing. Overload the subscript operator [ ] to provide access as in the following example:

AssociativeArray prices;
prices ["Toaster Oven"] = 19.95;
prices["Car Vacuum"] = 24.95
double total = prices["Toaster Oven"] + prices["Car Vacuum"];
cout << prices["Car Vacuum"]