The George Washington University
School of Engineering and Applied Science
Department of Electrical Engineering and Computer Science
CSci 131 -- Algorithms and Data Structures I -- Spring 2001
Project #5
Due Date: last day of class, Wednesday, May 2, 2001
This is a final deadline for all projects. No projects can be accepted
after this date!
In this project you will explore expression trees and expression parsing.
The new material is mostly that of Chapter 11.
Develop a calculator program that
-
prompts the user for an arbitrary expression containing floating-point
numbers, possible parentheses, and the operators +, -, *, and /
-
computes and displays the value of this expression.
The program should translate the incoming expression into a tree, then
evaluate the tree. If the expression is not well-formed, the program should
display an error message.
As an example, if the user enters (123.4-237.9)*47.7 the displayed
result will be -5461.65.
Hints:
-
The basic algorithm for translating from an expression to a tree is in
Program 11.1, but note that this program assumes single-letter variables,
not floating-point values, so you will have to modify it heavily.
-
For the tree node, use a variant record whose variant part can store either
an operator symbol or a floating point value.
-
You can reuse your generic stack package.
-
First use Get_Line to read the entire expression into a string,
then parse it out token-by-token. Ada can help you here: Ada provides Get
operations that read from a string instead of a file or keyboard. For details,
see the detailed discussion of text input in Annex A, Section 10, of the
Ada 95 Reference Manual. This is online, linked from http://www.seas.gwu.edu/~adagroup.
What to submit:
-
By now, you should be familiar with the various kinds of project elements,
documents, etc. Submit those elements that are appropriate for this project.