首页 > > 详细

CSCI 104讲解、辅导Data Structures、C++编程语言辅导、讲解c/c++讲解R语言编程|讲解留学生Prolog

CSCI 104 - Spring 2020
CSCI 104 - Spring 2020
Data Structures and
Object Oriented Design
HOMEWORK 5
Due: (See assignments page )
Directory name in your github
repository for this homework (case
sensitive): hw5
Any skeleton code for this
assignment will be available in
homework_resources/hw5 .
Do a git pull in your
homework-resources repo.
Then copy the homeworkresources/hw5
folder into your
hw-username repo and use the
skeletons provided to start work
in that hw5 folder.
Objective
In this assignment we will review recursion,
traversals, and heaps.
Introductory Notes
In this assignment you will need to submit:
Your completed tree traversal
(expression solver)
files/implementations in
hw5/traversal/ folder as well as a
Makefile in that folder to compile
your code to an executable exprtester
by running make in that folder.
Your heap operations answers in a file
named hw5.pdf in your hwusername/hw5
folder
Your completed heap files in the
hw5/heaps/ folder. You should have
some test file and a Makefile that
can be used to compile a test
program named heap-test by
running make in that folder.
Your completed eventsim
files/implementations in
hw5/eventsim/ as well as a Makefile
in that folder to compile your code to
an executable eventsim by running
make in that folder.
1. Binary Tree Traversals
(30%)
It is common to represent expressions (e.g.
arithmetic) as a tree where internal nodes
(non-leafs) are operators and leaf nodes are
values (literals (constants) or variables). In
this problem you will use a tree to represent
arithmetic expressions and perform several
operations on the tree that require recursive
traversals of the tree.
We will provide an expression reader that
will construct the tree so that you can focus
on the various processing operations.
Expression Format
This problem will process expressions that
contain the 4 basic arithmetic operations:
+ , - , * , / , integer literals, and
parentheses: ( , ) .
As an early example, consider ( ( 4 / 3 )
+ 96 + 104 ) would produce a tree:
Every unique operation (+,-,,/) must be
enclosed by parenthesis () (i.e. there is no
implicit order of operations allowed). So we
cannot write ( 2 * 4 + 3 ) , but instead
must write ( ( 2 * 4 ) + 3 ) . In addition,
every operator, parenthesis, or literal **must
be separated by spaces*.
So that the tree will contain nodes of the
same same type, each node will store a
string. That string will contain the operator
(e.g. "+") or the integer literal (e.g. "96") but
as a string. (You will convert to an integer
when you validate and/or solve the
expressions.)
Our reader roughly implements the following
rules/grammar for expressions:
op := '+' | '-' | '*' | '/'
literal := string
expr := literal | '(' expr ')' | expr op
expr
root-expr := '(' expr ')'
Each internal node of the tree should be an
operator and each leaf should be a numeric
string literal (string representing a valid
integer including negative numbers). The
provided reader will read in an expression
from any provided input stream (our test
program uses stdin by default but you can
use I/O redirection to redirect the contents
of a file as input) and return a pointer to the
root node or throw std::runtime_error if
the grammar is not met.
Expression Operations
You will implement three operations on the
expression tree that require recursive
traversals:
Validating the Expression: While our
expression reader detects most
syntax errors, it does not validate the
each leaf node contains a string that
can be converted to a valid integer.
Your task is to write a recursive
traversal of the tree that will return a
bool indicating that entire expression
contains valid integers as leaves. That
is all it needs to check for (no other
forms of errors). Consider which form
of traversal is most appropriate for
this task (pre-, in-, post-order). A
prototype for this function is provided
in the skeleton and you may not
change it. However, you may add
helper function(s), if necessary.
Printing the Expression: You should
implement a recursive traversal of the
tree that converts the internal tree
representation back to a correct/valid
text based representation and output
it to a provided std::ostream .
Assuming the tree represents a valid
expression, the text expression you
output should be correct, such that it
could be provided as input in a
subsequent run and generate the
same tree. Consider which form of
traversal is most appropriate for this
task (pre-, in-, post-order). A
prototype for this function is provided
in the skeleton and you may not
change it. However, you may add
helper function(s), if necessary.
Evaluating the Expression: You
should implement a recursive
traversal of the tree that evaluates the
expression and returns the integer
result. You may assume the tree
represents a valid expression.
Consider which form of traversal is
most appropriate for this task (pre-,
in-, post-order). A prototype for this
function is provided in the skeleton
and you may not change it. However,
you may add helper function(s), if
necessary. (Note: If the expression
contains a divide-by-0, you do not
have to handle it specially. Just let it
fault.)
Testing
We have provided a test-driver application
that you can use to verify your functions. It
will call our reader function and return the
pointer to the root of the tree or throw
std::runtime_error . It will then call your
functions to validate, print, and solve the
expression.
Other Requirements
You must use recursion to process
each node but can use a loop to
iterate through children.
You may not modify the signatures of
the functions we provide but may add
helper functions.
You should only edit expr-ops.cpp .
2. Heap Operations (10%)
You will answer several questions about
Heaps in this problem.
For this problem, you can choose to draw
this by hand and scan it (and submit as a
JPG or PDF), or to use some graphics
software (and produce a JPG or PDF), or
draw it using ASCII art (this may be a lot of
work). Name your file hw5.pdf .
Part a (3%)
Indicate whether the following arrays are
valid binary Min Heaps (assuming the root is
at index 0 of the array). For each array
which is not, indicate which child(ren)
violate the heap property (i.e. are out of
place).
[6, 2, 26, 24, 22, 20, 48, 46, 44]
[2, 16, 4, 50, 18, 5, 28, 71]
[2, 16, 4, 10, 18, 26, 28, 11]
Part b (5%)
Draw the tree representation of the following
binary Min Heap in its initial configuration,
and after each operation. Make sure to
clearly indicate each of your final answers.
This is a sequence of operations, meaning
one affects the next.
Initial Configuration: [2, 4, 6, 8, 10, 12,
14, 16]
Insert 3
Pop (top element)
Pop (top element)
Insert 5
Part c (2%)
Given the following array, perform the build
heap (make heap process) to convert the
array into a valid min-heap. Show the array
contents after each step. More specifically,
show what index you are calling
heapify/trickle-down on (e.g. heapify(8) )
and the entire array contents after each call.
[38, 8, 29, 15, 53, 20, 24, 18, 7 ]
3. Heaps (25%)
Build your own m-ary Heap class whose
public definition and skeleton code are
provided in the hw5 folder of the homeworkresources
with the interface given below.
Rather than specifying a specific type of
heap (Min- or Max-Heap) we will pass in a
PComparator (P for Priority) object so that if
the comparator object functor implements a
less-than check then we will have a minheap.
If the PComparator object functor
implements a greater-than check we will
have a max-heap.
template template >
class class Heap Heap
{
public public:
/// Constructs an m-ary heap for any m >= 2
Heap(int m, PComparator c = PComparator() );
// other stuff
};
You may use the STL vector container
if you wish. You should of course NOT use
the STL priority_queue class or
make_heap , push_heap , etc. algorithms.
You may add private helpers, if you like.
As you implement the heapify() process
when popping the heap, recall that a parent
would swap with its best child if the best
child is "better" than the parent. However,
what if we have a tie for the best child?
Choosing either to swap with is technically
fine, but for the sake of the next homework
problem where you will use the heap, let us
choose the left-most of the children tied for
the "best" (first one encountered if you are
iterating in order).
Notice we can provide a default template
type for the Comparator so that the client
doesn't have to specify it if they are happy
with the std::less (i.e. which assumes a
built-in operator< is available for type T
and calls it).
Notice the constructor also provides a
default value for the Comparator which is a
default-constructed Comparator. Default
parameter values will be used if the client
does not supply them. Also if a default
parameter is used then all parameters after
it must also have default values (i.e. default
parameters must be at the end of the
declaration). The last thing to note is you
only supply the default value in the
declaration of the function. When you
define the function (i.e. write the
implementation below) you would not
specify the default value again but just
leave the argument types/names. For
example, when implementing the function
you'd just define:
template template
Heap

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!