Due Friday April 20 at 11:59pm
In this half of the assignment, you will help implement a part of a symbolic algebra calculator. A symbolic algebra calculator is a kind of calculator that does not immediately evaluate the expressions you type in but instead lets you manipulate them symbolically.
You will implement the logic for manipulating and evaluating mathematical expressions.
You will be modifying the following file:
main.java.calculator.ast.ExpressionManipulators.java
Additionally, here are a few more files that you might want to review while completing the assignment (note that this is just a starting point, not necessarily an exhaustive list):
test.java.calculator.TestCalculator.java
main.java.datastructures.interfaces.IList.java
main.java.datastructures.interfaces.IDictionary.java
main.java.experiments.*
main.java.calculator.ast.AstNode.java
main.java.calculator.gui.ImageDrawer.java
main.java.calculator.interpreter.Environment.java
To get us started, let's look at what your finished program will look like.
The user can interactively enter commands in the bottom pane. These
commands can do different things, ranging from just evaluating expressions
to graphing actual output. The lines that start with
>>>
are lines where the user typed in input;
the following lines are the output of that operation.
Our code will manage most of the logic in this pane for you. Your job is to simply focus on evaluating expressions.
Let's take a closer look at an example run:
>>> 3 + 2 * 7
17
>>> x + y
x + y
>>> x := 1
1
>>> x + y
1 + y
>>> y := 2
2
>>> x + y
3
The users type input into the lines that start with
>>>
. The line that follows immediately
after is the output.
This example demonstrates the two core features we can perform using this calculator: evaluate math expressions (line 1) and symbolically work with variables (lines 7 - 17).
When we first typed in x + y
, we were unable to
evaluate or simplify the expressions because the variables x
and y
are currently unknown. Once both variables are defined,
we can evaluate this function.
To assign variables, we do varName := expression
. This
differs from how we assign variables in Java: we use :=
instead of =
, and we don't need to assign a type to this
variable. (All variables in our language are just mathematical expressions,
so there's no need).
Here is another example run:
>>> y := x + 3
x + 3
>>> y
x + 3
>>> x := 4
4
>>> y
7
>>> x := 8
8
>>> y
11
We define y
to be equal to the expression
x + 3
. What exactly that expression evaluates to depends
on the exact definition of x
.
Here is another example:
>>> y := x + 2 + 3 * sin(x) + (20 + 30)/70
x + 2 + 3 * sin(x) + 50 / 70
>>> y
x + 2 + 3 * sin(x) + 50 / 70
>>> x := 4
4
>>> y
6 + 3 * sin(4) + 50 / 70
>>> toDouble(y)
4.44387822836193
Notice that when we define y
and display it, we don't
evaluate the expression fully. By default, our calculator will
perform simplification only if it can get an exact result.
For example, we know evaluating sin
and division generally
does not produce exact results, so do not attempt to simplify those
particular expressions.
In this case, we could have simplified 50 / 70
further. However, for the sake of simplicity, we will follow a simpler
rule: we do not attempt to simplify division.
To get back an exact result, we need to use the toDouble(y)
expression.
More specifically, we attempt to simplify expressions involving addition, subtraction, and multiplication of two numbers. If you are interested in implemented more complex kinds simplification operations, you can do so for extra credit.
Finally, the payoff: by deferring evaluating the expression, we can manipulate expressions in interesting ways we wouldn't be able to do otherwise. For example:
>>> y := x^2 + 7*x + 10
x ^ 2 + 7 * x + 10
>>> plot(y, x, 0, 10, 0.5) // Plot y by varying x from 0 to 10 in steps of 0.5
// Output plot omitted
>>> derive(y, x) // Derive y with respect to x (extra credit)
2 * x + 7
These functions all work by taking the underlying expressions and manipulating them in some way.
So, how do we go about actually representing expressions like
x + 2 * sin(y)
in our code?
It turns out the most convenient representation is to store this as a tree:
This lets us easily preserve things like nesting and order-of-operations. We can also evaluate or manipulate this tree using the same kind of tree-manipulation algorithms you studied in CSE 143!
We call this sort of data structure an abstract syntax tree (AST). Each individual node in this tree is an AST node. An abstract syntax tree is similar to the binary trees that you've studied in CSE 143, with a few key differences:
sin(...)
) or any node that contains children (like
a + b
).
You should read the source code of AstNode.java
for
more information on what methods are available for you to use.
So, we can represent expressions as a tree of AstNodes, but what exactly does an AstNode look like?
There are three types of AstNodes:
Numeric nodes and variable nodes ought to be self-explanatory: they represent numbers and variables respectively. These types of nodes are guaranteed to always be leaf nodes.
Operation nodes are a little more abstract: they represent any kind
of node that might have one or more children. For example, something
like 3 + x
would be represented as an operation node
(+
) with two children: a numeric node (3
)
and a variable node (x
).
Another way of looking at operation nodes would be to consider them
exactly equivalent to function calls. So, the expression
sin(3)
would be represented as an operation node – as
a function call – with one argument.
(This means doing (3 + 2)
is really equivalent to calling
a function named +
, passing in two arguments! This trick of
treating everything as function calls helps us simplify our overall language.)
The AstNode
class contains methods you can call
to determine what type of node it is and to extract relevant
pieces of information.
We can represent expressions using abstract syntax trees, but how do we store variables?
We use a dictionary! Whenever the user defines a variable, we store
that variable name as a string and the corresponding expression in
your ArrayDictionary
. If a variable does not exist
in that dictionary, we say it's an unknown variable.
We will provide you with code that handles variable assignment: you only need to use the pre-populated dictionary you were given.
toDouble(...)
Task: Implement ExpressionManipulators.handleToDouble(...)
.
(Note: you can find ExpressionManipulators
in the
calculator.ast
package.)
First, you will implement handleToDouble(...)
, a function that
attempts to fully evaluate the given AST into just a single double.
This method will receive an operation node named toDouble
. This node
will contain a single child, which is the expression you are to convert into a double.
(So, this method might receive the AST node corresponding to toDouble(3.0 + 4.0)
.
You would then return the AST node corresponding to 7.0
).
For more details about the expected behavior of this function, see the comments in the method you need to implement.
Furthermore, you may assume that the expression AST you must convert to a double will consist only of the following types of nodes:
+
, -
,
*
, /
, and ^
(addition, subtraction, multiplication, division,
and exponentiation)
negate
operator. The "negate" operator
is used to represent expressions like -(x + 3)
(here, we negate x + 3
). We use the string
"negate" in these cases instead of "-" to avoid clashing
with the subtraction operation.sin
and
cos
.For example, the input to represent toDouble(3 + 4)
would be
Which would return a new node containing the value 7.0
. The representation of toDouble(-(a + b))
would be:
Which would return a node with the numeric value -(a + b)
, if a
and b
are defined.
Task: Implement ExpressionManipulators.handleSimplify(...)
.
This method is responsible for simplifying an AST node. For more
implementation details, see the comments in the handleSimplify(...)
method as well as the unit tests you have been provided.
You may make the same assumptions about the AST as you did in part 2a – the only difference is that instead of being given an operation node named "toDouble" that contains a single child, you will be given an operation named "simplify" that contains a single child.
Notes:
handleSimplify(...)
function many times while evaluating a
single expression, so make sure it's relatively efficient.NUM + NUM
, NUM * NUM
, and NUM - NUM
.
You may implement additional simplifications for extra credit – the
tests you were provided will accept a range of different answers in case you
decide to do this.For example, to evaluate simplify((5 + 6) + (7 - a))
with no variables defined,
we would pass in simplify
in the following diagram to handleSimplify(...)
:
Which will simplify the expression to a new tree containing the following:
Note that the method was not required to simplify the expression further down to 18 - a
.
plot(...)
Task: Implement ExpressionManipulators.plot(...)
.
As before, see the source code for additional implementation nodes.
Similar to before, you will receive an AST operation node named "plot".
However, this time, the node will have five children – see the
comments associated with plot(...)
for more details. The representation of the node produced by plot(3 * x, x, 2, 5, 0.5 + a)
is shown below (this would necessitate that the variable a
has been previously defined):
You may make the same assumptions about each child as you did in 3a and 3b.
Note: you are not responsible for drawing the actual chart yourself.
Instead, you should call the drawScatterPlot(...)
method
(see ImageDrawer
).
Task: complete a writeup containing answers to the following questions.
Note: your completed writeup MUST be in PDF format. You will not submit this writeup
via Canvas – instead, add it to your src/writeup
folder. (That way,
when you zip and submit the src
folder at the end of part 2, we'll be
able to look at your writeup along with your source code).
Your writeup will be graded partially on whether or not you produced a reasonable answer, and partially based on the clarity of your explanations and analysis.
While testing your DoubleLinkedList
and ArrayDictionary
classes, you should have discovered that your data structure needs to handle both
null and non-null entries or keys. Explain how you modified your code so it could
handle these two different types of inputs.
Justify the design decisions you made. (Your answer should be at most 1 to 2 paragraphs long).
In this question, you will run a variety of experiments and report back on the resulting behavior. Since this is the first assignment, we have written the assignments for you so all you need to do is run them. You will be asked to write your own experiments in future projects, so be sure to take some time to read the provided code and understand what's going on.
You can find the experiments in the analysis.experiments
package.
For each of the four experiments, answer the following:
Briefly, in one or two sentences, summarize what this experiment is testing. (Note: the experimental code deliberately has minimal comments. Treat this as an exercise in reverse-engineering unknown code.)
Predict what you think the outcome of running the experiment will be.
Your answer should be around one or two paragraphs. There is no right or wrong answer here, as long as you thoughtfully explain the reasoning behind your hypothesis.
Run the experiment code. Each Experiment*.java
file should
generate a CSV file in the experimentdata
folder
(it is possible that the 4th experiment will produce a warning; this is
can safely be ignored, as long as the CSV file in generated as described).
Import the CSV file into Microsoft Excel, Google Sheets, or any other
analysis of your choice and generate a plot of the data. Include this
plot as a image inside your writeup.
If the CSV file contains multiple result columns, plot them all in the same chart.
You will be graded based on whether you produce a reasonable plot. In particular, be sure to give your plot a title, label your axes (with units), include a legend if appropriate, and relabel the columns to something more descriptive then "TestResult".
How do your results compare with your hypothesis? Why do you think the results are what they were?
Task: submit answers to the following questions.
Each group member should answer and submit these questions independently at this canvas page.
You must submit your answers in either .txt
or
.pdf
form.
You can earn extra credit by extending your calculator in different ways. See the extra credit page for more details.
If you decide to complete any of the extra credit, describe what you implemented at the end of your group writeup.
The following deliverables are due on Friday April 20 at 11:59pm.
A single person from your partnership should
submit a zip file containing the entire contents of your src
folder
on Canvas.
Make sure that the src
folder contains the
following:
ExpressionManipulators.java
class.
Both partners should turn in a .txt
or
.pdf
file containing their answers to part 2e
on Canvas
if you haven't already. This is due at the same time as
the rest of your project. Note that if you wish to earn back credit from
part one as noted in
the syllabus,
those updates must be submitted within the zip file described above - we will
re-evaluate part 1 based off this submission.