Due Friday October 19 at 11:59pm. Submit via GitLab. If you intend to submit late, fill this late submission form before the deadline.
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:
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):
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
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
=, 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
y to be equal to the expression
x + 3. What exactly that expression evaluates to depends
on the exact definition of
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
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
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
more information on what methods are available for you to use.
You are not required to know how to build an AST expression
to complete this assignment. However, if you're curious, here's
how we would build the AST representing the expression
x + 2 * sin(y):
// Create 'sin' node IList<AstNode> sinParams = new DoubleLinkedList<>(); sinParams.add(new AstNode("y")); AstNode sinNode = new AstNode("sin", sinParams); // Create the 'multiply' node IList<AstNode> multiplyParams = new DoubleLinkedList<>(); multiplyParams.add(new AstNode(2.0)); multiplyParams.add(sinNode); AstNode multiplyNode = new AstNode("*", multiplyParams); // Create the final 'add' node: IList<AstNode> addParams = new DoubleLinkedList<>(); addParams.add(new AstNode("x")); addParams.add(multiplyNode); AstNode finalNode = new AstNode("+", addParams);
You may be wondering how exactly we go about converting arbitrary strings into an AST.
We've provided you the code to do this, and understanding how this process works is beyond the scope of this class, but if you're curious, this process is known as "lexing" and "parsing". A "lexer" takes a string and outputs a list of each distinct "token" in the stream. A parser takes this list of tokens and figures out how to convert it into a tree form.
We use a library called ANTLR which will automatically generate
a lexer and a parser for us based on a grammar that describes
what our language looks like. See the files in
if you want to know what our grammar looks like.
If you'd like to learn more about this whole process, feel free to ask the course instructor.
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
3 + x would be represented as an operation node
+) with two children: a numeric node (
and a variable node (
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.)
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
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.
(Note: you can find
ExpressionManipulators in the
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
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:
^(addition, subtraction, multiplication, division, and exponentiation)
negateoperator. 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.
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
b are defined.
This method is responsible for simplifying an AST node. For more
implementation details, see the comments in the
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.
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
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.
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
If you want to try implementing extra visualizations or charts (perhaps for extra credit? See below), here are some additional pieces of information that may help.
The calculator itself is built on top of Java Swing,
which is the same library that the
class from CSE 142 uses. This means that fundamentally,
the way we draw things is the same: we get and use a
Graphics object. See
ImageDrawer.getGraphics() for more details.
We use a library called "JFreeChart" to draw our
different charts. You can find documentation on how
to use this library online, and an example in the
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 and commit it to git. (That way,
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
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
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
(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?
A CSV file is a kind of text file formatted to contain tabular data. Each row of data goes on a separate line, and each cell in a row is separated by commas. (CSV stands for "comma separated value").
Since CSV files are just regular text files, you can open and view them using any text editor such as Eclipse. This makes CSV files a fairly popular way of exchanging data – they're easy to generate programatically, yet are understood by a wide variety of tools (such as Excel or Google Sheets).
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 a plain text (
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 October 19 at 11:59pm.Push all you commits to GitLab. We'll grade your the last commit before the deadline. If you wish to avail late day tokens, fill out this form: (form will be available soon).
Both partners should turn in a