The Problem Your job is to implement two versions of the evaluate static method
ID: 3565838 • Letter: T
Question
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 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 +, %u2013, *, 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
minus>
times>
divide>
plus>
expression>
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
Method
/**
* Evaluate the given expression.
*
* @param exp
* the {@code XMLTree} representing the expression
* @return the value of the expression
* {@code [exp is a subtree of a well-formed XML arithmetic expression] and
* [the label of the root of exp is not "expression"]}
*
* {@code evaluate = [the value of the expression]}
*
*/
private static int evaluate(XMLTree exp) {...}
/**
* Evaluate the given expression.
*
* @param exp
* the {@code XMLTree} representing the expression
* @return the value of the expression
* {@code [exp is a subtree of a well-formed XML arithmetic expression] and
* [the label of the root of exp is not "expression"]}
*
* {@code evaluate = [the value of the expression]}
*
*/
private static NaturalNumber evaluate(XMLTree exp) {...}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
minus>
times>
divide>
plus>
expression>
Explanation / Answer
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 +,
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.