1. Overview
A binary tree is a recursive data structure. We can define a tree as either being null, or containing data in its root, and having a pair of trees called its left and right subtrees, each of which is itself a tree.
In this assignment you will implement a symbolic calculator which stores arith- metic expressions in the form of binary trees (abstract syntax trees) in a symbol table. Input will be in reverse Polish notation (RPN), named so after its invention by Polish mathematician Jan Łukasiewicz. Hewlett-Packard calculators commonly use this notation. Infix notation, such as is used in Java, is harder to parse and will not be used. The operators to be implemented are : assignment of an expression, assignment a value, evaluation of an expression, and the usual four arithmetic oper- ators +, -, *, and /.
Reference : http://en.wikipedia.org/wiki/Reverse_Polish_notation
2. Program Specification
The program is specified in the format of a Unix man(1) page. NAME bitreecalc − binary tree RPN calculator
SYNOPSIS
bitreecalc[−e] [−ooutputfile] [inputfile...]
DESCRIPTION
Each line of input is read as a separate statement, and executed as it is read. An input line may have one of four formats : variable = expression
The RPN expression is converted into a tree and stored in the symbol ta- ble entry associated with the variable. A postorder traversal of the tree is then done in order to evaluate it, using the current values of all vari- ables. This new value is