Project: XMLTree Expression Evaluator
Objectives
- Familiarity with using recursion to evaluate arithmetic
expressions.
- Familiarity with using XMLTree objects and methods.
- Familiarity with using NaturalNumber objects and
methods.
The Problem
Your job is to implement two versions of the evaluate static
method to recursively evaluate arithmetic expressions represented as XMLTrees.
One version of the method evaluates the expression with ints
and the other version uses NaturalNumbers. The expressions
are stored in XML format (see below) so the program can load them as XMLTrees.
Arithmetic Expressions
The program supports arithmetic expressions with integer
operands, binary operators +, –, *, and /, and parentheses ().
The precedence rules are the standard ones from arithmetic (i.e.,
parenthesized expressions are evaluated first, then multiplicative
operators, and finally additive operators).
Generating XMLTree expressions
To generate the XML input files for your program, you can use a
program that allows the user to enter an arithmetic expression and
save it into the corresponding XML document. You can run this program
by importing it into Eclipse. First you need to download the project
archive, xml-expression-generator.zip, to your computer.
Click on this download
link and save the file somewhere on your hard drive where you can
easily find it. Make sure that you do not expand this archive.
If your browser automatically expands downloaded zip archives, that's
OK too. Just pay attention to the special instructions in the
following few steps. You may want to make a note of where you saved
it.
Import your new project in Eclipse by following these steps:
- From the File menu select Import....
- In the new window, expand General and select Existing
Projects into Workspace. Click Next.
- Click on the radio button next to Select archive file
and then click the Browse... button. (If the archive was
expanded when you downloaded the file to your own computer, click on
Select root directory... instead.)
- In the file selection window, find the xml-expression-generator.zip
file and select it. (If your browser expanded the archive, find the xml-expression-generator
directory instead.) Click OK.
- Click Finish.
To run the program, find the RunGenerator.java file in the src
folder in the project and run it as usual as a Java Application. Once
you start the program, you can enter an expression (the program only
allows the user to enter characters that are valid in an expression)
and save it to an XML document on the local drive (the Save
XML... button is active only when the text entered is a valid
arithmetic expression).
Format of the Input Expression XML Document
Here is an example of the expression XML document representing the
expression 12*(7-3)/6+8:
The top-level tag is <expression>. Nested inside there
can be 5 different tags: <plus>, <minus>,
<times>, <divide>, and <number>.
The first four represent the (binary) operators and the last one
represents the operands whose value is specified in the required
attribute value (assume operands can only be non-negative
integers). Each of the operator tags has exactly two nested tags and
no attributes. There are no text nodes. Note that the parentheses in
the original expression have disappeared because the XML document
already "encodes" the correct order of evaluation of the operators in
the given expression.
Setup
- Create a new Eclipse project by copying ProjectTemplate
or a previous project you have created, naming the new project XMLTreeExpressionEvaluator.
- Open the src folder of this project and then open (default
package). As a starting point you can use any of the Java files.
Rename it XMLTreeIntExpressionEvaluator and delete the other
files from the project.
- Follow the link to XMLTreeIntExpressionEvaluator.java,
select all the code on that page and copy it to the clipboard; then
open the XMLTreeIntExpressionEvaluator.java file in Eclipse
and paste the code to replace the file contents. Save the file.
Method
- Edit XMLTreeIntExpressionEvaluator.java to implement
the first version of the evaluate method using recursion.
This is the one that uses int for the operand type and
computes the value of the expression with Java's built-in integer
operators. Here is the contract:
As the requires
clause states, you can assume that the given XMLTree is a
well-formed XML expression and you do not need to check for errors.
You can use the Integer.parseInt(String)
static method to convert a String value into an integer.
- Run the XMLTreeIntExpressionEvaluator program to
test your implementation of evaluate.
- Copy XMLTreeIntExpressionEvaluator.java to create XMLTreeNNExpressionEvaluator.java.
- Edit XMLTreeNNExpressionEvaluator.java to implement
the second version of the evaluate method using recursion.
This is the one that uses NaturalNumber for the operand type
and computes the value of the expression with NaturalNumber's
methods. Make sure you update the contract and the implementation to
match the following:
- Run the XMLTreeNNExpressionEvaluator program to test
your implementation of evaluate.
- Add checks for the preconditions (requires clause) of all the
NaturalNumber methods you invoke in your solution that have
a precondition and make sure you output descriptive error messages.
Note that even though you can assume the given XMLTree is a
well-formed XML expression, it is possible that one or more of the NaturalNumber
methods may be called with a violated precondition (e.g., divide by
0). If you find any violated precondition, you should stop the
evaluation of the expression and report a fatal error. Use the components.utilities.Reporter's
fatalErrorToConsole method to report the error and make the
program terminate.
- Select your Eclipse project XMLTreeExpressionEvaluator
(not just some of the files, but the whole project), create a zip
archive of it, and submit the zip archive to the Carmen dropbox for
this project, as described in Submitting
a Project.
Additional Activities
Here are some possible additional activities related to this
project. Any extra work is strictly optional, for your own benefit,
and will not directly affect your grade.
- Both the XML expression generator program and the XML
expression document format support three extra operations: mod
(%), power (^), and root (v).
For example, the expression (2*17v3+4)^(31%5) results in the
following XML document: Update the evaluate method in XMLTreeNNExpressionEvaluator.java
so that it supports these operations as well.