I need help with this please! I have included the directions as well as the code
ID: 3778706 • Letter: I
Question
I need help with this please! I have included the directions as well as the codes any and all help will be appreacited THANKS!
Problem 1
There are two files supplied for you: myStack.h and myStackTesting.cpp.
In a separate (implementation) file, implement the functions and operators with prototypes found in “myStack.h”. Make no changes to myStack.h or myStackTesting.cpp.
Use myStackTesting.cpp to test your code. Submit only your file (where the implementations are).
Sample Output:
Empty stack S1: {} Stack S1 after 5 random inserts: {42, 68, 35, 1, 70} Press any key to continue . . .
After S2=S1 [testing '=='] : S1 and S2 are equal Press any key to continue . . .
After S2.push(-39); S1.pop(x); [Testing '=' and '=='] : Not equal : S1 : {42, 68, 35, 1} S2 : {42, 68, 35, 1, 70, -39} Press any key to continue . . .
Emptying S1 into S3 [Testing 'pop', 'isEmpty'] : Before: S1 : {42, 68, 35, 1} S3 : {} After: S1 : {} S3 : {1, 35, 68, 42} Press any key to continue . . .
Trying to pop from an empty stack: S1 is empty, nothing to remove Press any key to continue . . .
Submit the following problems on a separate text file.
Problem 2.
Write a recursive function implements f given by the recursive definition:
f(0)=10
f(1)=2
f(n)=2*f(n-2)+1 for n>1,
where n is an integer.
Problem 3. Binary Search
Given an already sorted array, how can one efficiently (i.e. with as few comparisons as possible) search whether an element is in the array or not? Binary search is one such method. Shown below is an iterative implementation of binary search for integer arrays.
// given a sorted integer array A of size arraySize // return true if x is found in the array, otherwise return false. bool binarySearch(int x, int A[], int arraySize) { int first=0, last=arraySize-1; //searching for x between indexes first and last while (first<=last) //while there is at least one element between first and last { int middle=(first+last)/2; //pick the middle index if (x<A[middle]) last=middle-1; //if x is smaller, search the lower half (between first and middle-1) else if (x>A[middle]) first=middle +1; //if x is larger, search the upper half (between middle+1 and last) else return true; //if x is the same, we found it and are done } return false; //if the loop concludes, it means we did not find x in the array }
Write a recursive implementation of binary search.
Hint : Function prototype
bool binarySearchR(int x, int A[], int first, int last)
Bonus Problem
Write the function in Problem 3 as a template function so you can search different types of arrays, such as arrays of characters, strings, doubles, etc.
These are the two files needed please dont change anything on them thanks!
myStackTesting.cpp
#include "myStack.h"
#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
myStack S1, S2, S3;
double x;
//testing push and <<
cout<<"Empty stack S1: "<<S1<<endl;
for (int i=0; i<5; i++)
{
x=rand()%100+1;
S1.push(x);
}
cout<<"Stack S1 after 5 random inserts: "<<S1<<endl;
system("pause");
//testing =, ==,
cout<<" After S2=S1 [testing '=='] :"<<endl;
S2=S1;
if (S2==S1)
cout<<"S1 and S2 are equal"<<endl;
else
cout<<"Error: == is not working properly"<<endl;
system("pause");
S2.push(-39); S1.pop(x);
cout<<" After S2.push(-39); S1.pop(x); [Testing '=' and '=='] : "<<endl<<endl;
if (S1==S2)
cout<<"Error: '==' or '=' is not working properly"<<endl;
else
{
cout<<"Not equal :"<<endl;
cout<<"S1 : "<<S1<<endl;
cout<<"S2 : "<<S2<<endl;
}
system("pause");
cout<<" Emptying S1 into S3 [Testing 'pop', 'isEmpty'] :"<<endl<<endl;
cout<<"Before:"<<endl;
cout<<"S1 : "<<S1<<endl;
cout<<"S3 : "<<S3<<endl<<endl;
while (!S1.isEmpty())
{
S1.pop(x);
S3.push(x);
}
cout<<"After:"<<endl;
cout<<"S1 : "<<S1<<endl;
cout<<"S3 : "<<S3<<endl;
system("pause");
cout<<" Trying to pop from an empty stack: "<<endl<<endl;
if (S1.pop(x))
cout<<"This better not print out"<<endl;
else
cout<<"S1 is empty, nothing to remove"<<endl;
system("pause");
return 0;
}
myStack.h
#ifndef MYSTACK_H
#define MYSTACK_H
#include <iostream>
using namespace std;
/*A stack is a data structure which consits of a list (array)
where elements are added and removed from one end of the list only (called the top of the list).
This means that the last element added will be the first one removed. This is known as LIFO (Last In First Out).
Example: If the stack content is {12, 134, 45, 78}.
The operation to add 42, called "push(42)" will result in : {12,134,45,78, 42}
Then operation to remove an element, called "pop()" will result in : {12,134,45,78}. If we run pop() again : The operation to add 42, called "push(42)" will result in : {12,134,45}
*/
class myStack
{
friend ostream& operator<<(ostream&, const myStack&);
//overloading the stream insertion operator. E.g., if S is a stack with content {12, 134, 45, 78}
//cout<<S should print out {12, 134, 45, 78}. If S is empty, cout<<S should print {}.
friend bool operator==(const myStack&, const myStack&);
//overloading the equality operator ==.
//For two stacks S1 and S2, S1==S2 returns true if S1 and S2 have the same elements in the stack.
public:
myStack(int=1000);
/* Default constructor. Sets the maxStackSize to the parameter value passed.
Allocates memory for data for maxStackSize elements. Sets top=-1. */
bool push(double x);
/*Inserts an element to the top of the stack if the stack is not already full. Update top (top++).
Returns true if it is succesful. Otherwise it returns false. */
bool pop(double& dataout);
/*Removes an element from the top of the stack if the stack is not empty. This element is assigned to dataout. Update top (top--)
Returns true if the operation is succesful*/
bool isEmpty(); //return true if the stack is empty -- i.e., no elements in the stack.
~myStack(); //Destructor.
const myStack& operator=(const myStack&);
//overload the assignment operator
protected:
int maxStackSize; // the maximum capacity of the stack
int top; // the index of the top element in the stack
double *data; // the data in the stack
};
#endif
Explanation / Answer
Please copy code carefully and refer to code comments for better undestanding.
Problem 1:
#include<iostream>
#include "myStack.h"
using namespace std;
myStack :: ~myStack() {}
myStack :: myStack(int a) {
top = -1;
maxStackSize = 1000;
data = new double[maxStackSize];
}
bool myStack :: push(double x){
if (top+1 < maxStackSize){
data[top+1] = x;
top = top+1; // incrementing stack size
return true;
}else{
return false; // stack reached to its max size
}
}
bool myStack :: pop(double & dataout){
if (top > -1){
dataout = data[top];
top = top - 1; // poping element from stack
return true;
}
return false; // stack is already empty
}
bool myStack :: isEmpty() {
if (top <= -1) {
return true;
}
return false;
}
bool operator==(const myStack& s1, const myStack& s2){
if (s1.top != s2.top){ // check size for both stack
return false;
}
for(int i = 0;i <= s1.top;i++){
if(s1.data[i] != s2.data[i]){ // if any mismatch occur that is stacks are not equal
return false;
}
}
return true;
}
ostream& operator<<(ostream& os, const myStack& stack){
for(int i = stack.top; i > -1; i--){
os << stack.data[i] << " "; // puting data in stream
}
return os;
}
const myStack& myStack :: operator=(const myStack & s1){
for(int i = 0;i < s1.top + 1;i++){
this->push(s1.data[i]); // copying stack values.
}
return *this;
}
PROBLEM 2:
#include<iostream>
#include<cstdio>
using namespace std;
int f (int n){
if (n == 0){
return 10;
}else if (n == 1){
return 2;
}
return 2*f(n-2) + 1; // recurring
}
int main()
{
// testing function
cout<<"f(2) = " << f(2)<<endl;
cout<<"f(3) = " << f(3)<<endl;
cout<<"f(4) = " << f(4)<<endl;
return 0;
}
PROBLEM 3:
#include<iostream>
#include<cstdio>
using namespace std;
// defining template
template <typename T>
bool binarySearch(T x,T A[], int first, int last)
{
if (last >= first)
{
int mid = first + (last - first)/2;
// If the element is present at the middle itself
if (A[mid] == x) return true;
// If element is smaller than mid, then it can only be present
// in left subarray
if (A[mid] > x){
return binarySearch(x,A, first, mid-1);
}
// Else the element can only be present in right subarray
return binarySearch(x,A, mid+1, last);
}
// We reach here when element is not present in array
return false;
}
int main()
{
// testing binary search
// searching in integer array
int arr[] = {2, 3, 4, 10, 40};
int x = 10;
int n = sizeof(arr)/ sizeof(arr[0]);
for(int i = 0;i < n;i++){
cout<< arr[i] << " ";
}
cout<<" Searching " << x << endl;
bool result = binarySearch(x, arr, 0, n-1); // Result 1 means found and 0 means not found.
cout<<"Result: " << result<<endl;
// searching in character array
char chr[] = {'a', 'b','e', 'f'};
n = sizeof(chr)/ sizeof(chr[0]);
for(int i = 0;i < n;i++){
cout << chr[i] << " ";
}
char xx = 'f';
cout<< " Searching " << xx << endl;
result = binarySearch(xx, chr, 0, n-1);
cout<<"Result: " << result<<endl;
return 0;
}