本次加拿大代写是C++数据结构和算法的一个assignment
1. (10 points) Complete the implementation of the evalPostFix() in the Expression.h
file to evaluate a postx expression. The function should recognize and use the +, -, *,
/ and ^ operators, as well as an average operator @ which receives three arguments and
returns their average (take average as the lowest in priority), and evaluate the expression
when = is encountered. It should require spaces between all operators and = and use the
stack, string and math.h libraries. If you encounter a case in which you are not sure how
to solve the problem, make reasonable assumptions and explain them in your report.
2. (10 points) Using what you have already implemented previously and a Finite State
Machine, implement isValidExpression() in the Expression.h file to verify whether
an expression (containing the same operators stated in Q1) is a valid expression of the
requested type (prefix, infix, or postfix).
3. (15 points) Modify the the queue class in the CircularQueue.h file to efficiently imple-
ment a queue class using a circular array. You may use a vector (rather than a primitive
array) as the underlying array structure.
4. (25 points) Modify the BinarySearchTree class in the BinarySearchTree.h file to im-
plement lazy deletion. Note carefully that this affects many of the routines. Especially
challenging are findMin and findMax, which must now be done recursively. Several of
the routines will have to be modified. You will have to:
add a ag in each node to indicate if it has been deleted
change the traversal code to bypass any node that has been deleted
insert must be modi ed to skip any deleted nodes and allow reinsertion by just
ipping the deleted ag
delete must be modi ed to set the deleted ag
change the findMin and findMax routines to work recursively
Make sure to comment each change in your code clearly so it is easy to see what you have
changed.
5. (20 points) implement the balance() function in BinarySearchTree.h and modify the
tree so that it always remains an AVL tree before and after deletions (when preforming
lazy deletion, we only balance the tree once we are really changing the tree structure,
not when modifying the ags). Add proper tests to make sure the tree remains balanced
upon modi cations.
