ENGN2912B Scientific Computing in C++ - Assignment 03: Prime Numbers, String and Expressions parser
Assignment 03
Summary
This assignment contains two problems. First, we will implement a simple
command-line application that calculates and displays prime numbers. Second,
we will implement a String class capable of storing strings of variable
lengths and use this class to write a function that parses mathematical
expressions and computes their result.
As usual, the goal of the assignment is to practice writing these functions from scratch to understand all details that such implementation entails. Therefore, students must not use existing library functions providing such implementations but to write them using control structures and simple operations.
Topics
The main concepts to practice in this assignment are:
- Standard input and output
- Memory management with
newanddelete - Character arrays
- Passing arguments by reference and by pointers
- Working with classes:
- Declaration and definition
- Constructors and destructors
- Data members
- Member functions
- Operators
Grading
The assignment grade is based on automatic testing results, adherence to the assignment rules, and specific details of the implemented solution.
Per problem points are as follows:
- Problem 1: 20 pts
- Problem 2: 80 pts
- String class: 40 pts
- Expression calculator: 40 pts
Automated tests check the output of command-line programs for different inputs.
They check some individual functions and classes independently from the
command-line programs. They also check if all allocated memory has been properly
deallocated when the program finishes. If any memory block remains allocated,
tests fail with a message like MemoryCheck: ERROR: X blocks leaked!.
General Instructions (command line)
These are generic instructions about how to compile the assignment from a command-line window.
- Download the starter code using
git clone <your repository url>. - Open a command line shell and execute
./build.shorbuild.batto generate the project files usingCMakeand compile the provided code. - Open any file you want edit with a text editor or C++ development environment (e.g. Visual Studio, Xcode) and add your code to them.
- Compile your code again with
./build.shorbuild.bat, or using the development environment. - Execute the programs and verify they work as expected based on the specific instructions for each problem.
- Repeat steps 3-5 as many times as desired.
- Once you are satisfied with the result, save your changes using a
git commitcommand. For examplegit commit -a -m "Complete assignment". - Upload your assignment using
git push.
You can use git commit and/or git push as many times as desired, either
to save work in progress or to improve your code incrementally.
Visual Studio Code
VSCode can be used to complete the assignment and in replacement of some of the steps in the command-line instructions. Detailed steps were given during lecture. A quick summary is to clone the repository as in step 1, then use "Open Folder" in VSCode to open the cloned repo.
Student comments
A file named NOTES.txt is included in this repository. Students may use
this file to write any comment about the assignment and its solution.
Problem 1: Prime numbers
Students must implement a command-line application called print_primes which
asks the user for a number indicating how many prime numbers are desired, and
then calculates and displays those prime numbers.
A prime number is a positive integer greater than 1 that is not a product of two smaller ones.
Students may place all their code within the provided main function, or split
it in one or more functions as they wish.
Problem 1 - Requirements
The submitted code must meet the following requirements:
- The program must display a prompt to the user asking how many primes to
calculate. It should say
How many primes?. - The program must read an integer
nfrom the standard input usingstd::cin. - It must calculate and display the first
nprime numbers. The first number to display is2, then3, and so forth. - All calculated primes must be stored in a dynamically allocated array.
Use
newanddeleteto manage the array memory. - Prime numbers must be displayed one per line as
prime: <number>, where<number>must be replaced by an actual prime number. See the examples below.
Problem 1 - Examples
$ ./build/prob1/Release/print_primes.exe
How many primes?
1
prime: 2
$ ./build/prob1/Release/print_primes.exe
How many primes?
4
prime: 2
prime: 3
prime: 5
prime: 7Problem 2: String class and expressions parser
This problem has two parts.
Part 1: variable length strings
In this section we will implement a String class capable of holding strings
of variable length. This is similar to the one discussed in lecture, but
instead of setting a fixed limit for the maximum string length, memory
must be dynamically allocated with a size appropriate to the string each
instance holds.
The class must support copy operations and some basic operators as described in the source code comments.
A command-line application named string_test is provided which students can
use to help validate their String class implementation. Instructions about how
to use this application is given in the source code.
Requirements
Students must do the following:
- Fill the implementation of the
Stringclass in the filesprob2/String.hppandprob2/String.cppfollowing the instructions in them. - The
Stringclass must support copies, assignment and equality operators, and other basic operations detailed in the assignment source code. In particular, memory for storing the string must be allocated in the heap with thenewoperator. The implementation must only include control structures and loops, as well as, simple mathematical operations. In particular, all the string operations such as computing its length must be implemented by students and not obtained with library functions such asstd:strlenandstr::stcpy.
Part 2: expressions parser
In this section, we will use our String class to implement a command-line
application expression_calc which solves simple mathematical expressions.
Different from cmd_calculator in an earlier assignment, this program takes
a single argument which is a mathematical expression, parses it, and computes
its result.
The program is strict in the expression format which must either be a numeric
constant or a binary operation. The left and right hand side of a binary
operation are also expressions. We can create complex expressions by composing
binary operations and constants at multiple levels. An exact definition of what
constitutes a valid expression is given in the file prob2/calc_functions.hpp.
A recommendation of how to implement the parser function is also given in the
source code.
Requirements
Students must do the following:
-
Complete the implementation of the function
parse_and_solvein the fileprob2/calc_functions.cpp. Its declaration and notes about its behavior are inprob2/calc_functions.hpp. -
Complete the implementation of the
expression_calcprogram in the fileprob2/expression_calc.cpp. The program takes a single argument which must be a valid expression and it displays its result. In any error situation,SOLVE:
= where
<expression>is the input expression given in as command line argument and<result>is a number which is the result the solving the expression. See the examples below.References
-
std::cin: standard input.
-
std::isdigit: checks if a character is a numeric digit.
-
std::atoi: converts text to an integer number.
-
std::atof: converts text to a floating point value.
