**The expressions return!!!**

In this project, you will be dealing with a tree data structure that can represent **mathematical expressions.** Donâ€™t worry, thereâ€™s no parsing this time, and the evaluation is far easier!

## Starting point

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!**

- Iâ€™ve given you a starting point, but

To compile and run, do:

```
javac *.java
java Driver
```

Youâ€™ll see that it prints out a bunch of 0s and `<not implemented>`

s. 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
**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`

.

- in which case its
- a
**Variable**name- in which case its
`_value`

is the variableâ€™s name.

- in which case its
- an
**Operator**- in which case its
`_value`

is one of these operators:`"+", "-", "*", "/",`

or`"^"`

- also,
- the operands to that operator.`_left`

and`_right`

are its children

- in which case its

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.

- check if the variableâ€™s name (
**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.

- recursively evaluate the

`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.

- it has an
- 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).

- you will pass that

`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);`

- makes a new
`Variable(String)`

- makes a new
`Expression`

node containing a variable name. - e.g.
`Expression e = Variable("num_people");`

- makes a new
`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`

.

- makes a new
`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 :)- parses a string into a tree of
`isOperator()`

,`isNumber()`

,`isVariable()`

- return
`boolean`

s saying what type of node this is. - e.g.
`if(expr.isOperator()) ...`

- return
`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.)

- for number nodes, parses the
`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?

- Donâ€™t forget to call

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
```

## Grading Rubric

**[5]:**Submission- Incorrectly submitted projects will lose all 5 points.
- Please follow the submission directions carefully. Thereâ€™s no reason not to.
*Itâ€™s 5 free points, people.*

**[15]:**`toString()`

**[10]:**`toPostfix()`

**[25]:**`evaluate()`

**[15]:**`reciprocal()`

**[15]:**`getVariables()`

**[15]:**`geometricMean()`

**[+10]:**`toNiceString()`

## Submission

You will submit a ZIP file named `username_proj5.zip`

where `username`

is your Pitt username.

**Do not put a folder in the zip file, just the following file(s):**

- All the
`.java`

files- Including any changes you made to
`Driver.java`

- Including any changes you made to
**If you did the extra credit, please also add a file named EC.txt**- It can be an empty file
- Itâ€™s just there to let the grader know you did it

Do **not** submit any IDE project files.

Submit to the Box folder at this link. Drag your zip file into your browser to upload. **If you can see your file, you uploaded it correctly!**

You can also re-upload if you made a mistake and need to fix it.