Data Structures-Project 5 Trees Solved

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 Number in 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 name in which case its _value is the variable’s name.

   an Operator in 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 boolean s 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]