The George Washington University
School of Engineering and Applied Science
Department of Computer Science
CSci 131 -- Algorithms and Data Structures I
Project #5
http://www.seas.gwu.edu/~csci131/spring02/131s02p5.html
Due Date: start of class, Wednesday, May 1, 2002
This is a final deadline. NO late projects can be accepted after this date!

This project depends on material from Chapter 11 of the data structures book.

In this project you will develop an interactive application that emulates the operation of a calculator that has a number of registers and supports complex calculations.

Abstract description of the calculator

Our calculator has six variables or registers.
  • The registers are named A, B, C, D, E, and F.
  • Each register can contain an expression made up of register names, floating point constants, parentheses, and the operators +, -, *, and /.
  • Assignment to a register is indicated by the = operator (as in the C language family).
  • All registers contain an expression of 0.0 by default.
Further, the calculator has three commands. These are:
  • CLEAR, which clears all registers
  • SET, which is followed by an assignment statement
  • EVAL, which is followed by a register name. EVAL evaluates the expression and displays the result.
Here is an example of a run of the calculator. The calculator responses are indented.

CLEAR
  OK
SET B = 3.0
  OK
SET E = 5.0
  OK
SET D = (B * E) / 2.0
  OK
EVAL D
  7.5
SET E = 4.0
  OK
EVAL D
  6.0
SET F = B + D)
  ERROR

Implementation

Here are some implementation requirements you must follow to get the proper educational value from the project.
  • Represent the commands by an enumeration type.
  • Represent the register names by an enumeration type, and the calculator "memory" by an array that is subscripted by this enumeration type.
  • Represent an expression internally by an expression tree.
  • Each node of the tree will have left and right pointers and a data record.
  • The data record will have four fields:
    • a "type code" indicating whether the node contains a variable, a constant, or an operator;
    • a field of the register-name type
    • a field of float type
    • a character field that can hold an operator
  • The application will read a line of input, parse it, and act according to the command:
    • If the command is CLEAR, clear the registers to empty trees
    • If the command is SET, determine which register is being set, then convert the expression to an expression tree using an algorithm similar to that in Section 11.6 of the text.
    • If the command is EVAL, evaluate the tree by an algorithm to be given in class.

Parsing the input line

We'll discuss simple input parsing in class.