JAVA

Your job is to implement two versions of the evaluate static method to recursively evaluate arithmetic expressions represented as XMLTrees. One version of 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. To run the program on stdlinux open a terminal window and type the command /class/software/bin/xml-expression-generator. (To run the program on your own computer, download the executable jar file xml-expression-generator.jar. On Windows and Mac computers, you should be able to run it by simply double-clicking the file. On any platform, you can run the program by opening a terminal window and typing the command java -jar xml-expression-generator.jar in the folder where you have saved the jar file.)

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

The top-level tag is . Nested inside there can be 5 different tags: , , , , and . The first four represent the (binary) operators and the last one represents the operands whose value is specified in the required attribute value. 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:

/**

* Evaluate the given expression.

*

* @param exp

* the {@code XMLTree} representing the expression

* @return the value of the expression

* @requires

 
 * [exp is a subtree of a well-formed XML arithmetic expression] and
 
 * [the label of the root of exp is not "expression"]
 
 * 

* @ensures evaluate = [the value of the expression]

*/

private static int evaluate(XMLTree exp) {...}

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:

/**

* Evaluate the given expression.

*

* @param exp

* the {@code XMLTree} representing the expression

* @return the value of the expression

* @requires

 
 * [exp is a subtree of a well-formed XML arithmetic expression] and
 
 * [the label of the root of exp is not "expression"]
 
 * 

* @ensures evaluate = [the value of the expression]

*/

private static NaturalNumber evaluate(XMLTree exp) {...}

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Update the evaluate method in XMLTreeNNExpressionEvaluator.java so that it supports these operations as well.