Solution to the proof for Assignment 3
===============================================================================

Let S(n) represent the following statement:
	If c is a reference to a ConditionNode which is the root of a valid 
	parse tree for a Condition and the tree contains n ConditionNodes, 
	then c.interpret() leaves on top of the stack the truth value for 
	this Condition.

PROVE: S(n) is true for all n >= 1.
PROOF: By induction on the number of ConditionNodes in the tree.


BASE CASE: Prove S(1) is true.

In this case the Condition must be of the form
"Expression < Expression", "Expression == Expression", etc.
Since the parse tree has been correctly built by
assumption, e1 and e2 must be non-null and point to valid
Expression parse trees, and c1 and c2 must be null.
The code invokes e1.interpret() and e2.interpret(), which
leave on the stack the correct value of the first and
second expression. The variable whichComparison must be
one of "<", "==", or ">", and in each case the code
assigns the correct value to "result" and pushes this
value on top of the stack (e.g. if whichComparison is "==",
the value left on the stack is "true" if the value of the
first Expression is equal to the value of the second Expression,
and similarly for the other two comparators.)


Let k be an arbitrary integer >= 1.

INDUCTION HYPOTHESIS: Assume S(i) is true for i = 1,2,...,k.


INDUCTION STEP: S(k+1) is true.

Consider a Condition whose parse tree has more than one
ConditionNode, that is, the root plus some others. The
Condition must be of the form !(Condition) or (Condition) or
(Condition && Condition) or (Condition || Condition).

Consider each case. 

Case (a): The expression is of the form !(Condition).
Then e1=e2=null, c1 is non-null, and c2=null.
The code invokes c1.interpret(). Since c1 points to
a ConditionNode with < k Condition nodes, by induction
c1.interpret() correctly returns on top of the stack
the Boolean value of the condition inside the parenthesis.
Since whichComparison must contain "!",
the code then assigns to "result" the negation of this value,
and this is pushed on the stack, which is correct.

Case (b): The expression is of the form (Condition). Just
like above, except there's no negation involved.

Case (c): The expression is of the form (Condition && Condition).
Then c1 and c2 are both non-null, the code invokes c1.interpret()
and c2.interpret(). By the inductive hypothesis both return the
correct Boolean value on top of the stack for the two conditions
that have to be "anded", and then the code assigns the "and" of the
two Boolean values to "result", which is pushed on the stack.

Case (d): The expression is of the form (Condition || Condition).
Similar to case (c).


INDUCTION CONCLUSION: S(n) is true for all n >= 1.