exam 2 class definitions and code questions

Question 1

what are the private members of the Darray class?

Answer 1

T *ptr;
int cap;

Question 2

make the default constructor for the Darray class.

Answer 2

template <typename>
Darray<T>::Darray(){
ptr = 0;
cap = 0;
}</T></typename>

Question 3

make a constructor for the Darray class that takes an int as a parameter.

Answer 3

template <typename>
Darray<T>::Darray(int capacity){
cap = capacity;
ptr = new T[cap];
}</T></typename>

Question 4

make the copy constructor for the Darray class.

Answer 4

template <typename>
Darray<T>::Darray(const Darray<T>& actual){
cap = actual.cap;
ptr = new T[cap];
for(int i = 0; i < cap; ++i){
ptr[i] = actual.ptr[i];
}
}</T></T></typename>

Question 5

make a swap function for the Darray class.

Answer 5

template <typename>
void Darray<T>::swap(Darray<T> & rhs){
T *temp = ptr;
ptr = rhs.ptr;
rhs.ptr = temp;
int tmp = cap;
cap = rhs.cap;
rhs.cap = tmp;
}</T></T></typename>

Question 6

make a method for the Darray class called resize that takes an int parameter and is a void function.

Answer 6

template <typename>
void Darray<T>::resize(int newCap){
int smaller = cap;
if(newCap < smaller){
smaller = newCap;
}
T *tmp = new T[newCap];
for(int i = 0; i < smaller; ++i){
tmp[i] = ptr[i];
}
delete[] ptr;
cap = newCap;
ptr = tmp;
}</T></typename>

Question 7

make a destructor for the Darray class.

Answer 7

template <typename>
Darray<T>::~Darray(){
delete[] ptr;
}</T></typename>

Question 8

overload operator[] for the Darray class so that it takes an int as a parameter and is non const.

Answer 8

template <typename>
T& Darray<T>::operator[](int i){
return ptr[i];
}</T></typename>

Question 9

overload operator[] for the Darray class so that it takes an int as a parameter and is const.

Answer 9

template <typename>
T Darray<T>::operator[](int i) const{
return ptr[i];
}</T></typename>

Question 10

make a method for the Darray class called capacity that returns the capacity of ptr.

Answer 10

int Darray<T>::capacity() const{
return cap;
}</T>

Question 11

what are the private variables for the Stack class?

Answer 11

T s[size];
int tos; //top of stack

Question 12

make a method for the Stack class called isEmpty that takes no parameters and returns whether the Stack is empty.

Answer 12

bool Stack::isEmpty() const{
return (tos == -1);
}

Question 13

make an in-line default constructor for the Stack class.

Answer 13

Stack() : tos(-1){}:

Question 14

make a method for the Stack class called isFull that takes no parameters and returns whether the Stack is full.

Answer 14

template <typename>
bool Stack<T>::isFull() const{
return (tos >= size);
}</T></typename>

Question 15

make a method for the Stack class called push that pushes an item onto the Stack.

Answer 15

template <typename>
void Stack<T>::push(const T& item){
assert(!isFull());
s[++tos] = item //increment then return
}</T></typename>

Question 16

make a method for the Stack class called pop that returns the newest item in the Stack and ‘pops’ it.

Answer 16

template <typename>
T Stack<T>::pop(){
assert(!isEmpty());
return s[tos--]; //return then decrement
}</T></typename>

Question 17

make a method for the Stack class called pop that returns the newest item in the Stack.

Answer 17

template <typename>
T Stack<T>::top(){
assert(!isEmpty());
return s[tos];
}</T></typename>

Question 18

write a method for the String class called infix_to_postfix that uses a Stack variable and returns the postfix version of the equation entered.

Answer 18

String infix_to_postfix(const char expr[]){
Stack<String> s;
char token;
String lhs, rhs, op;
int i = 0;
while(expr[i] != 0){
token = expr[i];
\++i;
if(token == ')'){
rhs = s.pop();
op = s.pop();
lhs = s.pop();
s.push(lhs + rhs + op);
}
else if(token !+ '('){
String temp = " ";
temp[0] = token;
s.push(temp);
}
}
return s.pop();
}</String>

Question 19

write a method for the String class called infix_to_prefix that uses a Stack variable and returns the prefix version of the equation entered.

Answer 19

String infix_to_prefix(const char expr[]){
Stack<String> s;
char token;
String lhs, rhs, op;
int i = 0;
while(expr[i] != 0){
token = expr[i];
\++i;
if(token == ')'){
rhs = s.pop();
op = s.pop();
lhs = s.pop();
s.push(op + lhs + rhs);
}
else if(token !+ '('){
String temp = " ";
temp[0] = token;
s.push(temp);
}
}
return s.pop();
}</String>

Question 20

write a helper method for the EvalPostFix method called isoperand that returns whether a character is an operand.

Answer 20

bool isoperand(char ch){
return (ch == ‘+’ || ch == ‘-‘ || ch == ‘/’ ||
ch == ‘*’);
}

Question 21

write a helper method for the EvalPostFix method called EVAL that evaluates an expression.

Answer 21

int EVAL(int lhs, char op, int rhs){
switch(op){
case ‘+’: return lhs + rhs;
case ‘-‘: return lhs - rhs;
case ‘/’: return lhs / rhs;
case ‘*’: return lhs * rhs;
}
return 0;
}

Question 22

make a method for the String class called EvalPostFix that evaluates the postfix expression.

Answer 22

int EvalPostFix(const char& expr[]){
Stack<int> s;
int i = 0;
while(expr[i] != 0){
if(!isoperand()){
int lhs, rhs;
rhs = s.pop();
lhs = s.pop();
s.push(EVAL(lhs, expr[i], rhs);
}
else{
s.push((int(ch) - int('0'));
}
\++i;
}
return s.pop();
}</int>

Question 23

write a recursive method for the Fibonacci sequence.

Answer 23

int fib(int n){
if(n <= 2){
return 1;
}
else{
return fib(n - 1) + fib(n - 2);
}
}

Question 24

write a recursive method to find a factorial.

Answer 24

int nfact(int N){
if(n <= 1){
return 1;
}
else{
return nfact(N - 1);
}
}

Question 25

write an enum for the pole class (towers of hanoi)

Answer 25

enum poleName {left, right, middle};

Question 26

what are the private variables for the pole class (towers of hanoi)?

Answer 26

poleName p (enum for the poles)

Question 27

write the in-line function definition for the default constructor for the pole class.

Answer 27

pole(){};

Question 28

write the in-line function definition for a constructor for the pole class that takes a poleName as a parameter.

Answer 28

pole(poleName x) : p(x) {};

Question 29

write the in-line function definition for the output operator for the pole class that takes an ostream and a pole as parameters.

Answer 29

friend std::ostream& operator<<(std::ostream& out, pole rhs){ switch(rhs.p){ case left: out << "left"; break; case right: out << "right"; break; case middle: out << "middle"; break; } return out; }

Question 30

write a free function called move that is recursive and performs the towers of hanoi operations using the pole class.

Answer 30

void move(int n, pole src, pole aux, pole dest){ if(n <= 1){ std::cout << "move disk from" << src << "to" << dest << std::endl; else{ move(n-1, src, dest, aux); std::cout << "move disk from" << src << "to" << dest << std::endl; move(n-1, aux, src, dest); } }

Question 31

what are the private variables for the queue class (no dynamic memory).

Answer 31

int front int back bool empty T q[SIZE]; const int SIZE = 100;

Question 32

make an in-line definition for the default constructor for the queue class.

Answer 32

queue(): front(0), back(0), empty(true) {};

Question 33

make an in-line definition for the method isEmpty for the queue class.

Answer 33

bool isEmpty() const {return empty;};

Question 34

make an in-line definition for the method isFull for the queue class.

Answer 34

bool isFull() const {return back == front && !empty;};

Question 35

make a method for the queue class called enqueue that takes a T item and adds it to the queue.

Answer 35

template void queue::enqueue(const T& item){ assert(!isFull()); q[back] = item; back = (back + 1) % size; empty = false; }

Question 36

make a method for the queue class called dequeue that takes no parameters deletes and returns the first item from the queue.

Answer 36

template T queue::dequeue(){ assert(!isEmpty()); T result = queue[front]; front = (front + 1) % SIZE; if(front == back){ empty = true; } return result; }

Question 37

what are the public data members of the node class?

Answer 37

T data; node *next;

Question 38

what are the private data members of the stack class with dynamic memory?

Answer 38

node *tos; (top of stack)

Question 39

make an in-line definition for the default constructor of the stack class with dynamic memory.

Answer 39

stack(): tos(0) {};

Question 40

make an in-line definition for a method called isEmpty for the stack class with dynamic memory.

Answer 40

bool isEmpty() const {return tos == 0;};

Question 41

make an in-line definition for a method called Top for the stack class with dynamic memory that returns what is at the top of the stack.

Answer 41

T top() const {assert(!isEmpty()); return tos -> data;};

Question 42

make a method called push for the stack class with dynamic memory that adds an item to the top of the stack. Include requires and ensures.

Answer 42

//REQUIRES: tos -> x1 -> x2 -> ... -> xn -> 0 //ENSURES: tos -> item -> x1 -> x2 -> ... -> xn -> 0 template void stack::push(const T& item){ assert(!isFull()): node *temp = new node item; temp->next = tos; tos = temp; }

Question 43

make a method called pop for the stack class with dynamic memory that removes an item from the top of the stack. Include requires and ensures.

Answer 43

//REQUIRES: tos -> x1 -> x2 -> ... -> xn -> 0 //ENSURES: tos -> x2 -> ... -> xn -> 0 template T stack::pop(){ assert(!isEmpty()); T result = tos -> data; node *temp = tos; tos = tos -> next; delete temp; return result; }

Question 44

make the destructor for the stack class with dynamic memory.

Answer 44

template stack::~stack(){ while(tos != 0){ node *temp = tos; tos = tos -> next; delete temp; } }

Question 45

make a copy constructor for the stack class with dynamic memory.

Answer 45

template stack::stack(const stack& actual) : stack(){ if(actual.tos == 0){ return; } tos = new node(actual.tos->data); node *bottom = tos; node *temp = actual.tos->next; while(temp != 0){ bottom->next = new node(temp- >data) bottom = bottom->next; temp = temp->next; } }

Question 46

make the swap method for the stack class with dynamic memory.

Answer 46

template void stack::swap(const stack& rhs){ node *temp = tos; tos = rhs.tos; rhs.tos = temp; }

Question 47

make a method call isFull for the stack class with dynamic memory that returns whether the stack is full.

Answer 47

template bool stack::isFull() const{ node *temp = new(std::no throw) node(); if(temp == 0){ return true; } delete temp; return false; }

Question 48

write an in-line definition for the default constructor for the queue class with dynamic memory.

Answer 48

queue() : beginning(0), end(0) {};

Question 49

what are the private variables for the queue class with dynamic memory?

Answer 49

node *beginning; node *ending;

Question 50

make an in-line definition for the overloaded operator= for the queue class with dynamic memory that is canonical.

Answer 50

queue& operator=(queue rhs){swap(rhs); return *this;};

Question 51

make an in-line definition for the isEmpty method for the queue class with dynamic memory.

Answer 51

bool isEmpty() const {return beginning == 0;};

Question 52

write a method for the queue class with dynamic memory called enqueue that adds an item to the queue. Include requires and ensures.

Answer 52

//REQUIRES: beginning -> x1 -> ... -> xn <- end && !isFull() //ENSURES:: beginning -> x1 -> ... -> xn -> item <- end template void queue::enqueue(const T& item){ assert(!isFull()); if(beginning == 0){ beginning = new node(item); ending = beginning; } else{ ending -> next = new node(item); ending = ending -> next; } }

Question 53

write a method for the queue class with dynamic memory called dequeue that removes the first item from the queue. Include requires and ensures.

Answer 53

//REQUIRES:: beginning -> x1 -> x2 -> ... -> xn <- end && !isEmpty() //ENSURES:: beginning -> x2 -> ... -> xn <- ending template T queue::dequeue(){ assert(!isEmpty()); node *temp = beginning; T result = beginning -> data; beginning = beginning -> next; if(beginning == 0){ end = 0; } delete temp; return result; }

Question 54

write a method for the queue class with dynamic memory called front that looks at the front item in the queue.

Answer 54

template T queue::front(){ assert(!isEmpty()); return beginning -> data; }

Question 55

write a destructor for the queue class with dynamic memory.

Answer 55

template queue::~queue(){ node *temp; while(beginning != 0){ temp = beginning; beginning = beginning -> next; delete temp; } }

Question 56

make a copy constructor for the queue class with dynamic memory.

Answer 56

template queue::queue(const queue& actual) :queue(){ if(actual.isEmpty()){ return; } beginning = new node (actual.beginning -> data); node *temp = actual.beginning -> next; while(actual.beginning != 0){ ending = new node(temp -> data); ending = ending -> next; temp = temp -> next; } }

Question 57

make the swap method for the queue class with dynamic memory.

Answer 57

void queue::swap(const queue& rhs){ node *temp = beginning; beginning = rhs.beginning; rhs.beginning = temp; temp = end; end = rhs.end; rhs.end = temp; }

Question 58

make an isFull() method for the queue class with dynamic memory.

Answer 58

bool queue::isFull() const{ node *temp = new(std::no throw) node(); if(temp == 0){ return true; } delete temp; return false; }