Due Date: May 1, 1997

The fifth project involves writing a program that evaluates statements of an expression language. Statements consist of an arithmetic expression followed by a list of assignments. Assignments are separated from the expression and each other by commas. A semicolon terminates the input. The arithmetic expressions should be fully parenthesized infix expressions containing floating point literals and variables. The valid operators are +, -, *, /. Tokens can be separated by any number of spaces. You may assume that all operators including the assignment have at least one space before them and after them. The numeric literals can be signed. Variable names must begin with an alphabetic character, followed by any number of alphanumeric characters. An example of valid input is shown below:

(Value + 4.0) - X3 / -3.0, Value := 0.0, X3 := 10.0;

The program should read in the arithmetic expression and encode the expression as a binary expression tree (sects. 11.5, 11.6), not as the strings supplied to define them. The type definitions required are the following:

  TYPE Operators IS (Add,Subtract,Multiply,Divide);

  TYPE Node_Types IS

   (Operator_Type,Variable_Operand,Constant_Operand);

  TYPE Nodes(Node_Type: Node_Types := Operator_Type) IS RECORD

    CASE Node_Type IS

      WHEN Operator_Type =>

        Operator: Operators;

       WHEN Variable_Operand =>

        Variable: String;

      WHEN Constant_Operand =>

        Operand: Float;

    END CASE;

  END RECORD;

  TYPE TreeNode;

  TYPE Tree IS ACCESS TreeNode;

  TYPE TreeNode IS RECORD

    Left: Tree;

    Data: Nodes;

    Right: Tree;

  END RECORD;

You can use Program 11.1 as a starting point for the translator that converts from infix notation to binary trees. Note that this program uses expressions consisting of only single-letter variables and operators, so you'll need to parse the variable names and constants as you did with the constants in Project 4.

As the expression is read in, the variable names should be placed in a symbol table. The symbol table should be implemented using the Binary_Search_Trees_Generic package, Programs 11.2-11.9, in the textbook. Add a Replace procedure to the package. It should be instantiated for the following record, the Variable field being the key:

  TYPE Symbol IS

    RECORD

      Variable: String;

      Value: Float;

    END RECORD;

After the expression has been parsed, the variable assignments should be parsed and the values of the variables should be placed into the symbol table using the Replace procedure. Finally the expression should be evaluated recursively. The result of the evaluated expression should be a floating number. Division by zero should be detected, and an appropriate error message issued. Input containing uninitialized variables should be reported as an error. If a variable is assigned multiple values, the last assignment applies. You may assume that all input statements are syntactically correct. Test data which will adequately test the program should be chosen.