Question

STRICT DOWNVOTE IF NOT DONE FULLY, WILL REPORT ALSO IF COPY PASTED OR MODIFIED ANSWER Develop a class, using templates, to provide functionality for a set of recursive functions. The functions specified as recursive must be written recursively (not iterativly). The UML class specifications are provided below. A main will be provided. Additionally, a make file will need to be developed and submitted. ● Recursion Set Class The recursion set template class will implement the template functions. recursionSet -length: int -*mySet: myType -MAX_VALUE = 500000 static const: int -LIMIT = 1000 static const: int +recursionSet() +recursionSet(const recursionSet&) +~recursionSet() +getSetLength() const: int +generateElements(int): void + getElement(int) const: myType +setElement(int, myType): void +readValue(const string) const: int +printSet() const: void +operator == (const recusrionSet&): bool +tak(myType, myType, myType) const: myType +printSeptenary(myType) const: void +squareRoot(myType, myType) const: myType -recSqRoot(myType, myType, myType) const: myType +recursiveSum() const: myType -rSum(int) const: myType +checkParentheses(string) const: bool -recChkPar(string, int, int) const: bool +recursiveInsertionSort(): void -recInsSort(int, int): void -insertInOrder(myType, int, int): voidYou may add additional private functions if needed (but, not for the recursive functions). Note, points will be deducted for especially poor style or inefficient coding. Function Descriptions • The recursionSet() constructor should set the length to 0 and mySet pointer to NULL. • The recusrsionSet(const recursionBucket&) copy constructor should create a new, deep copy from the passed object. • The ~recursionSet() destructor should delete the myType array, set the pointer to NULL, and set the size to 0. • The setElement(int, myValue) function should set an element in the class array at the given index location (over-writing any previous value). The function must include bounds checking. If an illegal index is provided, a error message should be displayed. • The getElement(int) should get and return an element from the passed index. This must include bounds checking. If an illegal index is provided, a error message should be displayed and a 0 returned. • The getSetLength() functions should return the current class array length. • The printSet(int) function should print the formatted class array with the passed number of values per line. Use the following output statement: cout << setw(5) << mySet[i] << " • "; Refer to the sample executions for formatting example. The readValue(string) function should prompt with the passed string and read a number from the user. The function should ensure that the value is 3 1 and £ MAX_VALUE. The function should handle invalid input (via a try/catch block). If an error occurs (out of range or invalid input) an appropriate message should be displayed and the user re- prompted. Example error messages include: cout << "readSetLenth: Sorry, too many " << "errors." << endl; cout << "readSetLenth: Error, value " << cnt << " not between 1 and " << numMax << "." << endl; • Note, three errors is acceptable, but a fourth error should end the function and return 0. The generateList(int) function should dynamically create the array and use the following casting for rand() to fill the array with random values. mySet[i] = static_cast(rand()%LIMIT); • • • The printSeptenary(myType) function should print the passed numeric argument in Septenary (base-7) format. Note, function must be written recursively. The recursiveSum() function will perform a recursive summation of the values in class data set and return the final sum. The function will call the private rSum(int) function (which is recursive). The rSum(int) function accepts the length of the data set and performs a recursive summation. The recursive summation is performed as follows: rSum ( position )= • { array[ 0] array[ position ] + rSum ( position−1) if position = 0 if position > 0 The tak(myType) function should recursively compute the Tak 1 function. The Tak function is defined as follows: tak ( x , y , z) = { z tak ( tak ( x−1, y , z) , tak ( y−1, z , x) , tak ( z −1, x , y ) ) 1 For more information, refer to: http://en.wikipedia.org/wiki/Tak_(function) if y≥ x if y < x• • The squareRoot(myType, myType) function will perform a recursive estimation of the square root of the passed value (first parameter) to the passed tolerance (second parameter). The function will call the private sqRoot(myType,myType,myType) function (which is recursive). The private recSqRoot(myType,myType,myType) function recursively determines an estimated square root. Assuming initially that a = x, the square root estimate can be determined as follows: recSqRoot ( x , a , epsilon) = • • • • • { 2 if ∣ a − x ∣ ≤ epsilon a 2 (a + x) sqRoot x , , epsilon 2 a ( ) if ∣ a 2 − x ∣ > epsilon The recursiveInsertionSort() function should sort the data set array using a recursive insertion sort. The recursiveInsertionSort() function should verify the length is valid and, if so, call the recInsSort() function to perform the recursive sorting (with the first element at 0 and the last element at length-1). The recInsSort(int, int) function should implement the recursive insertion sort. The arguments are the index of the first element and the index of the last element. If the first index is less than that last index, the recursive insertion sort algorithm is follows: ▪ Recursively sort all but the last element (i.e., last-1) ▪ Insert the last element in sorted order from first through last positions To support the insertion of the last element, the insertInOrder() function should be used. The insertInOrder(myType, int, int) function should recursively insert the passed element into the correction position. The arguments are the element, the starting index and the ending index (in that order). The function has 3 operations: ▪ If the element is greater than or equal to the last element in the sorted list (i.e., from first to last). If so, insert the element at the end of the sorted (i.e, mySet[last+1] = element). ▪ If the first is less than the last, insert the last element (i.e., mySet[last]) at the end of the sorted (i.e., mySet[last+1] = mySet[last]) and continue the insertion by recursively calling the insertInOrder() function with the element, first, and last-1 values. ▪ Otherwise, insert the last element (i.e., mySet[last]) at the end of the sorted (i.e., mySet[last+1] = mySet[last]) and set the last value (i.e., mySet[last]) to the passed element. The checkParentheses(string) function should determine if the parentheses in a passed string are correctly balanced. The function should call the private recChkPar(string, int, int) function (which is recursive) The recChkPar(string, int, int) function should determine if the parentheses in a string are correctly balanced. The arguments are the string, an index (initially 0), and a parenthesis level count (initially 0). The index is used to track the current character in the string. The general approach should be as follows: ◦ Identify base case or cases. ◦ Check the current character (i.e., index) for the following use cases: ▪ if str[index] == '(' → what to do then ▪ if str[index] == ')' → what to do then ▪ if str[index] == any other character → what to do then Note, for each case, increment the index and call function recursively.

Answer 1

PLEASE HIT AN UPVOTE

// CS 202 Assignment #11
// Recursion Set - Provided Main.

// ----------------------------------------------------------------------------
// Incldues

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <limits>

#include "recursionSet.h"

using namespace std;

// ----------------------------------------------------------------------------
// Main program to test the class functions.

int main()
{
// ----------------------------------------------------------------------------
// Declarations and display of simple header.

const char *bold = "\033[1m";
const char *unbold = "\033[0m";
const char *green = "\033[32m";
const char *red = "\033[31m";
const char *underline = "\033[4m";

string bars = "";
bars.append(60, '-');

cout << endl;
cout << bold << underline << "CS 202 – Recursion Set Program" <<
unbold << endl << endl;

// ----------------------------------------------------------------------------
// Test recursive ackerman() function.

cout << bars << endl;
cout << "Tak Function:" << endl << endl;

recursionSet <long int> tst1;

cout << " tak(18,12,6): " << tst1.tak(18,12,6) << endl;
cout << " tak(10,7,5): " << tst1.tak(10,7,5) << endl;
cout << " tak(70,60,54): " << tst1.tak(70,60,54) << endl;
cout << " tak(70,60,52): " << tst1.tak(70,60,52) << endl;
cout << " tak(70,60,53): " << tst1.tak(70,60,53) << endl;
cout << " tak(70,60,51): " << tst1.tak(70,60,51) << endl;
cout << " tak(23,16,5): " << tst1.tak(23,16,5) << endl;

// ------------------------------------------------------------------------------
// Test square root function.

cout << endl << endl;
cout << bars << endl;
cout << "Square Root Function:" << endl << endl;

const double epsilon = 0.0001;

double num1 = 25.0;
double num2 = 2.0;
double num3 = 6561.0;
double num4 = 39871.0;
double userNum = 0.0;

recursionSet <double> tst2;

cout << "Square Root of " << num1 << " is "
<< tst2.squareRoot(num1, epsilon) << endl;
cout << "Square Root of " << num2 << " is "
<< tst2.squareRoot(num2, epsilon) << endl;
cout << "Square Root of " << num3 << " is "
<< tst2.squareRoot(num3, epsilon) << endl;
cout << "Square Root of " << num4 << " is "
<< tst2.squareRoot(num4, epsilon) << endl;

cout << endl;
string pmt1 = "Enter number: ";
userNum = static_cast<double>(tst2.readValue(pmt1));

if (userNum > 0)
cout << "Square Root of " << userNum << " is "
<< tst2.squareRoot(userNum, epsilon) << endl;

// ----------------------------------------------------------------------------
// Test recursive sum function.

cout << endl << endl;
cout << bars << endl;
cout << "Recursive Sum Function:" << endl << endl;

recursionSet <int> tst3;

cout << "-------" << endl << "Set #1:" << endl;
tst3.generateElements(15);
tst3.printSet(8);
cout << endl << endl;
cout << "The sum is: " << tst3.recursiveSum() << endl;
cout << endl;

cout << "-------" << endl << "Set #2:" << endl;
tst3.generateElements(75);
tst3.printSet(8);
cout << endl << endl;
cout << "The sum is: " << tst3.recursiveSum() << endl;

// ----------------------------------------------------------------------------
// Test recursive sort function.

cout << endl << endl;
cout << bars << endl;
cout << "Recursive Insertion Sort:" << endl << endl;

recursionSet <float> tstFlt;

cout << "------------------" << endl << "Set #2 (sorted):" << endl;
tst3.recursiveInsertionSort();
tst3.printSet(8);

cout << endl << endl;
cout << "------------------" << endl << "Set #3 (unsorted):" << endl;
tstFlt.generateElements(12);
for (int i=0; i<12; i++)
tstFlt.setElement(i, tstFlt.getElement(i)+0.5);
tstFlt.printSet(8);
cout << endl << endl;
cout << "------------------" << endl << "Set #3 (sorted):" << endl;
tstFlt.recursiveInsertionSort();
tstFlt.printSet(8);

// ----------------------------------------------------------------------------
// Test copy constructor.
// copy previous tst3 object into tst4 object.

cout << endl << endl;
cout << bars << endl;
cout << "Copy Constructor Test:" << endl;

recursionSet <int> tst4(tst3);

cout << endl;
if (tst3 == tst4)
cout << "Copy Constructor Succeeded." << endl;
else
cout << "Copy Constructor Failed." << endl;

cout << endl;
tst4.setElement(73, 0); // error
tst4.setElement(42, 1); // error
tst4.setElement(3, 2); // modify the copy
tst4.recursiveInsertionSort();

cout << endl << "Modified List (16 replaced with 2):" << endl;
tst4.printSet(8);

cout << endl << endl;
if (tst3 == tst4)
cout << "Error, copy of set not modified." << endl;
else
cout << "Success, copy of set modified." << endl; // it should be modified

// ----------------------------------------------------------------------------
// Test recursive printSeptenary() function.

cout << endl << endl;
cout << bars << endl;
cout << "Septenary Function:" << endl << endl;

recursionSet <long long> tst5;
int num5 = 0;
string pmpt5 = "Enter integer value ";
int sNum1 = 123, sNum2=234, sNum3=1200000;

cout << "Septenary value of " << sNum1 << ": ";
tst5.printSeptenary(sNum1);
cout << endl;
cout << "Septenary value of " << sNum2 << ": ";
tst5.printSeptenary(sNum2);
cout << endl;
cout << "Septenary value of " << sNum3 << ": ";
tst5.printSeptenary(sNum3);
cout << endl << endl;

num5 = tst5.readValue(pmpt5);
if (num5 > 0) {
cout << "Septenary value of " << num5 << ": ";
tst5.printSeptenary(num5);
}

// ----------------------------------------------------------------------------
// test parentheses checking function

cout << endl << endl;
cout << bars << endl;
cout << "Check Parentheses Function" << endl <<endl;

recursionSet <string> tst6;

string parens[] = { "(()()())", // good
"if ((x ==y) && (z==q))", // good
"( ( ( ) ) ( ( ( ) ) ) )", // good
"( ( (asdf) ) ( ( ( ) ) ) )", // good
"( ( ( ) )", // bad
")(", // bad
"( ( !fasle ) )", // good
"if ((x ==y) && (z==q)", // bad
"if () && () else ())", // bad
"if (() && ()" // bad
};
int parensLen = sizeof(parens) / sizeof(parens[0]);

// loop to check all provided strings
for (int i=0; i < parensLen; i++) {
cout << "The parentheses in string: " << parens[i];
if (tst6.checkParentheses(parens[i]))
cout << green << " : is correctly balanced." <<
unbold << endl;
else
cout << red << " : is not correctly balanced." <<
unbold << endl;
}

// ----------------------------------------------------------------------------
// Done...

cout << endl;
cout << bars << endl;

return 0;
}

// ====================================================================