Homework: C++ Expression Implementation

Due: Monday, December 9, 2024, at 11:59pm

Assignment Goal

This assignments provides practice with basic C++ functionality, including inherited class implementation and use of smart pointers. C++ code is used along side Python code to generate a plot.

Synopsis

You will be writing a small C++ library to represent and manipulate equations with variables. Although we can already write math expressions in C++, we cannot directly express an equation with variables like x or m. For example, if we want to represent the equation y = mx + b, we could create a function that takes x, m, and b, but this is time consuming and inflexible.

Instead, we are creating a base class called Expr which represents a math expression, which may or may not contain variables. Examples of expressions include m*x+b, 42+374, x, etc.

Expr is the base class which is extended via inheritance to be a number (Num), variable (Var), or a sum of two other Expr’s (Sum). You will also add a multiplication expression (Prod) and an exponential expression (Pow).

Note: Because Expr is the base class, we usually deal with expressions as pointers to some expression. This library uses smart pointers, so you should use shared_ptr<Expr>. We also included a handy typedef, so you can just say ExprPtr if you prefer. We also provide two helper functions var() and num() which create a shared_ptr to a Var and a Num, respectively. You should use only smart pointers and make_shared; do not use malloc or new.

For example, the expression m*x+b would be represented as a Sum of two other Expr‘s. The first Expr is a Prod of two Vars m and x, the second just a single Var b.

To make this library convenient to use, we will be overloading the standard C++ operators for multiplication and addition, as well as using the ^ operator to represent exponentiation, so that you can write Expr expressions as C++ code.

This data structure is a form of an “Abstract Syntax Tree” (AST): the AST specifies the structure of the math notation we write. For example, the expression m*x + b requires knowledge of order-of-operations to recognize that the multiplication is performed before the addition; the AST explicitly represents this relationship as a tree. We will be taking advantage of C++’s standard operator precedence rules to construct the correct AST for the expression we write.

As an example, consider the expression x+2*y^3+5. In AST form, it looks like this:

Set-Up

Before you get started, ensure that your set-up is up-to-date and appropriate.

You should do this assignment using cancun, including g++ and make.
Ensure that your repository is up-to-date and committed. (You can use git status to determine if there are outstanding changes, and git add and git commit if you are unsure.)
Use git pull upstream main to pull the newest commit from the upstream repository. This will give you access to the hw9 folder containing the materials for this assignment.
The last part of this assignment uses matplotlib and numpy. While the provided Makefile takes care of this on cancun you may wish to set up for this step by running pip3 install --user numpy and pip3 install --uer matplotlib.

You will do this assignment in your new hw9 folder. You should get into the habit of committing and pushing code frequently.

Provided Files

Your hw9 folder contains the following files:

Expr.h: Declares the Expr class and its derivatives. You will edit this code to include new derived classes.
Expr.cc: Defines functions for the Expr class derivatives. You will edit this code to finish defining specific supporting functions and operator over-rides.
main.cc: Code to exercise the Expr classes. You will uncomment this code as you go.
Plot.cc: Uses the Expr classes to generate data points to plot various expressions. You will edit this code to generate data for a new equation.
plot_png.py: Python generates a plot from csv data.
helpers.h: Declares var and num functions for use in main.
helpers.cc: Defines var and num functions for use in main.
Makefile: A Makefile to compile your code and run the demo.
cpplint.py: The linter you will use to check your coding style.

Your Task

Part 1: Set Variables for Num, Var, Sum

If you run make right now, it should print a warning about not returning anything in setVariables(), but it will generate the ./main executable. If you run ./main it will segfault. We need to implement the setVariables() function for Num, Var, and Sum

This is a recursive function which will replace some or all of the Var nodes with Num nodes, based on the map from variable names to double values. In other words, it is used to create a new expression that replaces the variables with the corresponding numerical values, if those exist in the map. It should not perform any numerical computations. The goal of this function is to ultimately return an actual number.

For example, in main.cc they call exp1->setVariables(values), which should return an expression with all the “x” variables replaced with 42 and all the “y” variables replaced with “43”.

Note: setVariables() always returns a copy, it should never modify the current object. setVariables() has two base cases: Num and Var.

The implementation for Num is the simplest, it should just return a copy of itself, wrapped with a shared_ptr. Var should check if its own variable name is in the map passed in. If it is not, then just return a copy of itself, wrapped with a shared_ptr. If its own variable name is in the map, it should return a wrapped Num object owned by a shared_ptr where the number is the value associated with its variable name. Sum is the recursive case; just call setVariables() on the left and right expression.

Tip: Feel free to take inspiration from existing clone() functions!

After doing this, you should be able to recompile and not get a segmentation fault when running ./main.

Part 2: Prod and operator*()

Now, implement a Prod node representing multiplication (product). You should see the class in Expr.h. This process should be pretty similar to implementing Sum since they are both operators which have two expressions. You will have to add the functions to Expr.cc:

Prod::Prod(shared_ptr<Expr> left, shared_ptr<Expr> right)
shared_ptr<Expr> Prod::clone() const
shared_ptr<Expr> Prod::setVariables(const std::map& values) const
shared_ptr<Expr> operator*(shared_ptr<Expr> lhs, shared_ptr<Expr> rhs) double Prod::evaluate() const
For operator*(shared_ptr<Expr> lhs, shared_ptr<Expr> rhs), check out the operator+(shared_ptr<Expr> lhs, shared_ptr<Expr> rhs) implementation provided in Expr.cc.

After doing this you should be able to uncomment the next block of code in main.cc. When you run make it should compile ./main. Running ./main, you should see the actual output match the expected output.

Part 3: Pow and operator^()

Now, implement a Pow node representing an exponent (e.g. x^2). The Pow class is in Expr.h, but it doesn’t have any of the methods or data members in it, so fill those in. It should be very similar to Sum and Prod. Implement each of those functions as well as operator^().

Tip: The pow() function in <cmath> can be useful for calculation! The library is included in Expr.cc for you.

You should now be able to uncomment all of main.cc. Run make and ./main to ensure that your output matches the expected output.

Part 4: plot.cc

If you run make plot, it should compile plot.cc into plot_csv, then it will run ./plot_csv and the provided ./plot_png.py which will generate line.csv and line.png. The graph shown in the image file should look something like this:

This code should work on cancun, but, if you get error messages about the python libraries you can run pip3 install --user numpy; pip3 install --user matplotlib.

The provided write_file() function plots the y coordinates of an equation, given a set of x points, then writes it into a given filename. Your job is to use write_file() to plot the y coordinates of a curve equation: 0.5x^2 + 3, writing it into curve.csv. This should only be a few lines, and the code should look very similar to the line example.

Hints

Tip: You can search for "TODO" in any of the files to find the specific areas you will be editing.

Note: Pay attention to the data types of the specified functions. This code makes use of references, and also sometimes requires returning a Vector (not a pointer to a Vector). You should take care to create your Vectors and return them appropriately.

Code Quality

You should ensure that your code follows typical guidelines regarding variable naming. You should include comments as necessary for any tricky parts of your solution, and may also use comments to highlight changes you make while solving this homework. You will also want to use cpplint.py to check that your code complies with the style guidelines before submitting.

Assessment

This assignment will be worth 50 points. Your code will be evaluated by an autograder. You are welcome to submit again in order to achieve a better score, but, you should use your main exectuble to test your code before you do so. Be sure to fix warnings or errors that occur during compilation, and then compare the ouput of your code to the target output. You should be able to uncomment all of main during this testing. You may also view your generated figure to ensure that it looks reasonable.

Turning In

You will submit this homework to the Gradescope HW9: C++ Expression Implementation, via Gitlab. You should first commit your work to your repository, including your Vector.cc file. These files will be located in the hw9 folder at the top level of your repository.

Once you locate the Gitlab assignment you will tap the "GitLab" button on the bottom:

Picture of Gradescope interface highlighting the Gitlab button as opposed to the Upload button

Find your 374 repository in the list, and Submit Project.

Picture of Gradescope submission interface

Once you submit your code the autograder may take some time to run. You may resubmit for a higher grade, but your should always do as much testing as possible on your own platform before resubmitting.