CS0445 Project 5 Tree data structure that can represent mathematical expressions Solved

Download and extract these materials. Contained are:

Expression.java, the file you will modify.
ExpressionError.java, just an exception type.
Driver.java, which is used to test Expression.I’ve given you a starting point, but you should expand upon this and add more tests!
To compile and run, do:

javac *.java
java Driver

You’ll see that it prints out a bunch of 0s and <not implementeds. You need to fix that :)


Expression trees ¶
Like I showed in class, trees come up a lot in representing languages, such as math and programming languages.

The Expression class represents a node in an expression tree. Each instance of Expression can be one of three things:

a Numberin which case its _value is a string representation of the value.
you can use getNumberValue() to easily convert that string to a double.
a Variable namein which case its _value is the variable’s name.
an Operatorin which case its _value is one of these operators: "+", "-", "*", "/", or "^"
also, _left and _right are its children - the operands to that operator.
There are no “bracket” nodes; order of operations is entirely determined by the tree’s structure.

Here are some examples of mathematical expressions and the trees which represent them:



Compare the last two trees. You can think of parentheses as saying, “force this part of the expression to be a sub-tree.”


Your task ¶
Open Expression.java and look through it. There are already some methods written, but there are several stubbed-out ones with TODO inside them.

Each method gives you practice writing very common kinds of tree algorithms: visiting all the nodes in a tree; searching through a tree; creating a new tree which is a modification of an old one; and building a tree from scratch.

The next section documents some methods I wrote for you that will be helpful in writing these.

String toString() ¶
returns a human-readable infix string representation of this expression tree.
for numbers: return the string representation of its value.
for variables: return the variable name (the _value member).
for operators: return a string of the form "(left op right)", where:left is the string representation of the _left member
op is this operator (the _value member)
right is the string representation of the _right member
the result will have lots of parentheses. that’s correct :)
String toPostfix() ¶
returns a human-readable postfix string representation of this expression tree.
this should be a very slight modification of toString().
don’t forget to call toPostfix() recursively.
there should be no parentheses in the output.
double evaluate(Map<String, Double variables) ¶
given a set of variables, evaluate the expression tree and return the result.
for numbers: return the numerical value of the node (getNumberValue()).
for variables:check if the variable’s name (_value) exists in the set of variables, using variables.containsKey()
if not, throw an ExpressionError with a descriptive error message.
if so, return the value from variables.get().
Here is the documentation for Map. You can find the docs for containsKey() and get() there.
for operators:recursively evaluate the _left and _right children, using the same variables argument to them.
based on this operator (_value), perform the right calculation on those two values and return the result.
Expression reciprocal() ¶
returns a completely new expression tree that is the reciprocal of this one.
you will not be making recursive calls to reciprocal(), but you should use clone() where appropriate.
there are 3 cases:numbers: return a new number node whose value is the reciprocal.
division: return a new division node whose children are cloned and swapped.
everything else: return a new division node whose children are 1 and a clone of this.
Set<String getVariables() ¶
returns a set containing all the unique variable names which appear in the expression tree.
the code I gave already creates the Set<String for you.it has an .add() method that you can use to add Strings to it.
you will have to write a private recursive method to actually find the variables, and have this call that one.you will pass that variables set as an argument to it.
think about how each kind of node will change the set (if at all).
static Expression geometricMean(double[] numbers) ¶
You may not use quickParse() to implement this method. Sorry ;)

creates an Expression that represents the geometric mean of the array of numbers given as an argument.
the resulting Expression should be of the form:(numbers[0] * numbers[1] * ... * numbers[n-1]) ^ (1 / n)
where n is the length of the array.
(it’s OK to assume that the array is always at least 1 item long.)
use the Number(), Operator(), and reciprocal() methods to create the expression.
making the chain of multiplications can be done iteratively or recursively.it’s a fun little puzzle :)

The methods I wrote for you ¶
Number(double)makes a new Expression node containing a number.
e.g. Expression e = Number(3.1415);
Variable(String)makes a new Expression node containing a variable name.
e.g. Expression e = Variable("num_people");
Operator(Expression, String, Expression)makes a new Expression node containing an operator, and which points to two children.
e.g. Expression e = Operator(Number(4), "/", Number(5)); for the expression 4 / 5.
quickParse(String)parses a string into a tree of Expression nodes. supports +-*/^ and regular parentheses ().
e.g. Expression complex = Expression.quickParse("1 / (5*x^2 + 3*x - 9)");
quickParse has very little error checking and will likely crash or give weird results with erroneous input. But it’s really there for testing purposes, so just give it valid expressions please :)
isOperator(), isNumber(), isVariable()return booleans saying what type of node this is.
e.g. if(expr.isOperator()) ...
getNumberValue()for number nodes, parses the _value member into a double.
for operator and variable nodes, will probably crash. (that’s why it’s private.)
clone()makes a complete copy of an expression, recursively.
have a look at how this method is implemented!

Testing ¶
Driver.java has a small amount of code in it to test your Expression methods. However it does pretty minimal testing. Like it tells you, TEST MORE THOROUGHLY!!! Use Expression.quickParse() to easily create test cases.

Here are the outputs I got from my implementation:

toString: (((4.0 * x) + (y / 9.0)) + 12.0)
toPostfix: 4.0 x * y 9.0 / + 12.0 +
evaluate: 55.0
reciprocal: (1.0 / (((4.0 * x) + (y / 9.0)) + 12.0))
reciprocal(num): 0.14285714285714285
reciprocal(div): (10.0 / x)
getVariables: [x, y]
geometricMean: (((((4.0 * 9.0) * 3.0) * 7.0) * 6.0) ^ 0.2)
it evalutes to: 5.3868466094227525


Extra Credit [+10] ¶
String toNiceString() ¶
Turns the expression into a nice string. ;)
This is like toString() but it will only put parentheses where needed.
Hints:Don’t forget to call toNiceString() recursively.
Decide whether to put parentheses around each of an operator’s children.
Think about when you, as a human, need to put parentheses in an expression. What is the rule there? What does it have to do with?
Done correctly, if you just have toString() call this method, the relevant lines of the above output would now look like:

toString: 4.0 * x + y / 9.0 + 12.0
reciprocal: 1.0 / (4.0 * x + y / 9.0 + 12.0)
reciprocal(div): 10.0 / x
geometricMean: (4.0 * 9.0 * 3.0 * 7.0 * 6.0) ^ 0.2