Hints and Clarifications for HW2

This page will be updated as hints are added.

parsePostfix() - stacks: you must write an implementation of a stack yourself. Using a library class or other existing code is disallowed. (See the general homework guidelines.)

parsePostfix() - modifying the tree in-place: parsePostfix must modify its receiver in-place. After calling, say, parsePostfix("xx*"), the tree should "forget" what it was before and "become" the tree for x*x. It is up to you whether to implement the ExpTree class as a container class, as a tree node class, or in some other way. In any case, an instance of ExpTree must be able to represent an empty tree when needed.

parsePostfix() - error checking: The only error checking you should perform is that the stack operations are invoked correctly, namely (a) when popping the stack, it must be non-empty, and (b) at the end of the input, the stack contain exactly one tree, the result. If these conditions are not satisfied, an exception or error must be raised and the program should abort.

parsePostfix() - input symbols: Also, as you read the input expression, any symbol that is not "x", a digit, or an operator should be simply ignored (skip such symbol and continue to the next).

parsePostfix() - use of the stack: the ExpStack used in this method should be temporary. There should be no references to it remaining after the method returns.

derivate(): Here are some derivation rules. Assume that the derivative of an expression f is f' and the derivative of g is g'. Then:

the derivative of the expression f+g is the expression f'+g'
the derivative of f*g is (f*g') + (f'*g)
the derivative of f/g is ((f'*g) - (f*g')) / (g*g)

Your derivate method must create and return a new tree, rather than modify the tree that is the receiver of the method.

Extra credit opportunity. Write the following method in the ExpTree class: ExpTree simplify(). When applied to an ExpTree t, this method should return a new tree that is a simplification of t. To simplify a tree:

replace all subexpressions containing only numbers with the result of the corresponding computation;
- e.g.: (3+5)/2 simplifies to 4
(you may need to adjust your data structure to allow for non-integral or multi-digit computation results)
replace all subexpressions of the form 0+f, 1*f, f+0, or f*1 with f
- e.g.: 1*(x+3) simplifies to x+3
replace all subexpressions of the form 0*f or f*0 with the number 0
- e.g.: (x+x)*0 simplifies to 0
(optional) if f and g are the same tree, replace f-g with 0

If a simplification step (one of the above) opens other simplification opportunities, they must also be pursued.

e.g.: ((x*0) + 5) simplifies to 5

For full extra credit, however, you are allowed to traverse the tree only once.

This task is worth 15 "extra credit" points. We strongly suggest to implement fully the required specs (and save away a copy of your code) before proceeding to this task.