documentation calc_tree

This paper gives further information on calc_tree - the data structure used for 
keeping track of the computing processes in the basic calculator.

a calc_tree is a binary tree. every node has either none, one or two children. 
nodes with zero children are called leaves; nodes with at least one children 
are referred to as (internal) nodes.

Internal Nodes represent arithmetic operations while leaves cover the numbers 
of the operation. Image the calculation
	1 + 3
Following the above definitions, this can be displayed as a tree in (only) two 
ways:
   +      +
  / \    / \
 1   3  3   1
By arrangement, a tree is constructed from left to right - therefore the above 
calculation would lead to the first tree.

A tree is subject of change while the user does the calculation. The smallest 
possible piece of information is named token.
A token is either
	- a bracket
	- or a number and a following operation
	
precedence:

So far, it is not obvious why using trees is an advantage. But when doing 
arithmetics, we have to pay attention to precedence. E.g. in 3+4*5 we have to 
first multiply 4 by five and than add the result to 3. Trees give us the 
possibility to observe precedence.

Remember that the operations are the nodes of our tree. Let current_node be the 
last node inserted into the tree and current_token the number/operation pair to 
add. If the precedence of the current_token is greater than the one of the 
current_node, the operation in current_token becomes the right child of 
current_token and the number the left child of this new node.
Otherwise, if precedence of current_node is greater or equal than the one of 
current_token, we follow the path from current_node to the root of the tree as 
long as the precedence of the visited node is greater or equal the precedence 
of current_token. Insert the operation either as new root (if all were greater 
or equal) or between the last node of greater or equal precedence and its 
parents.

assume the following input to our calculator: 1-3^2*4+3/3= (the result is -34)
this input split up into tokens: 1-, 3^, 2*, 4+, 3/, 3=
these tokens joined to a tree:

1.  -	2.  -	3.  -	4.    +  5.     +    6.     +
   /       / \     / \       /        /   \       /   \
  1       1  ^    1  *      -	     -     /     -     /
            /       /      / \      / \   /     / \   / \
           3       ^      1  *     1  *  3     1  *  3   3
                  / \       / \      / \         / \
                 3   2     ^   4    ^   4 		^   4
						  / \      / \	  	   / \
						 3   2    3   2	 	  3   2
                 	 
of course, we won't build this tree first and do the computation at the end. 
Everytime, we insert a token of smaller precedence, we can reduce the tree by 
doing some computation. In step 1 and 2, no computation is possible. Bu e.g. 
in step 3 we could do 3^2 and replace the node ^ by the leave 9.

The next "operation" we have to deal with are brackets. The behave different
from the ordinary arithmetic operations addition, subtraction etc. Consider the
computation 1+(3+2) on a paper, you would first regard 3+2 as a stand-alone
computation, solve it and replace the bracket expression by the result. Speaking
in terms of calc_tree, brackets can be handled in a own tree, we will call it a
sub tree:

1. +    2. +   SUBTREE: +  +  SUBTREE = 5   3. +   4. 6
  /       / \          /  / \                 / \
 1       1   *        3  3   2               1   5

        * sub
        tree
        goes
        here
	
A last thing to note is associativity. Most operations are left associative,
meaning they are processed from left to right (3/2/2 is treated as (3/2)/2. But
there are also right associative operations, e.g. power: 2^3^2 = 2^(3^2) !=
(2^3)^2! We have to take care of precedence when reducing the calc_tree.

**
** NEW
**

proposal to enhance calc_basic to do "everything" resp to handle a formular mode:

calc_basic isn't able to handle functions at the moment. But it already knows
brackets, which are done in an own sub tree. We define a function as a
function taking a double argument and returning a double argument. Therefore
we can state that every function is applied to an expression enclosed by
brackets resp - if we use the terms of this document - every function is applied
to a sub tree. Additionaly we can say that every bracket expression has a
function associated with (identity function!).
calc_basic gets an additional stack, called the function_stack which holds the
functions to apply to the sub trees on the sub_tree_stack. After completing a
sub_tree, the next function on the function_stack is applied.

We have to consider yet, how far this requires a change of the way tokens are
passed to the calc_basic code.
