In the RecursiveMethods class, you are required to implement the following methods using recursive solutions (no looping statements):
computePI(int n) - One remarkably simple formula for approximating the value of is the so-called MadhavaLeibniz series: see image.
Note that the result of the series is a quarter of . The accuracy of the approximation is dependent on the value of n. This method takes an int parameter n and calculates the value of PI, rather than PI/4. Pay attention to the sign (positive or negative) of each term.
evaluateSignsRec(CharStack signs) - In Homework 2, you implemented the evaluateSigns method which takes a CharStack of signs and evaluates the expression on the stack with XOR operations. This time, the method takes the same parameter as the input, performs one round of evaluation, and then saves the result on the original stack. For example, in the following signs stack on the left, after one round, it becomes the one on the right (Note the order of the signs in the new stack): see image.
Do NOT create any auxiliary data structure, including but not limited to array(s), queue(s), and list(s). Primitive variables are okay.
reverseStringRec(String s) - This method reads a string and returns the string in the reversed order.
numOccurrencesRec(LNode node, int n, int key) - This method takes as parameters a reference to the head of a linked list, a position specified by n, and a key. It returns the number of occurrences of the key in the linked list beginning at the n-th node. If n = 0, it means you should search in the entire linked list. If n = 1, then you should skip the first node in the list. Do NOT create any additional nodes or any other auxiliary structures (for instance, an array). Do NOT alter the data field of any nodes.
Note that you are only supposed to touch the above methods. You are NOT allowed to create any other methods, instance variables, or make any changes to methods other than these four methods or files other than "RecursiveMethods.java".
You are provided with a test driver implemented by "TestRecursiveMethods.java" (Do not make any changes to this file!) so there is no need to write your own.
Once you have completed the methods, you can run the test. You should create a plain text file named "output.txt", copy and paste the output (if your code crashes or does not compile, copy and paste the error messages) to this file and save it.
Test 1: computePI(1) ==> [Passed]
Expected: 4.0
Yours: 4.0
Test 2: computePI(4) ==> [Passed]
Expected: 2.8952
Yours: 2.8952
...
Test 8: evaluateSignsRec("--+++" (from top to bottom)) ==> [Passed]
Expected: "-+--" (from top to bottom)
Yours: -+--
Test 9: evaluateSignsRec("+--+++-+-+-" (from top to bottom)) ==>
[Passed]
Expected: "+-+--+++++" (from top to bottom)
Yours: +-+--+++++
...
Test 18: numOccurrencesRec([45->25->73->25->19->25->43->25], 1, 25) ==>
[Passed]
Expected: 4
Yours: 4
Test 19: numOccurrencesRec([45->25->73->25->19->25->19->45], 4, 19) ==>
[Passed]
Expected: 2
Yours: 2
Total test cases: 19
Correct: 19
Wrong: 0
// The RecursiveMethods class that implements several recursive solutions
public class RecursiveMethods {
// This method takes an int as the parameter and estimates the result of the
// Madhava–Leibniz series. The result is then considered as an approximation
// of pi. The method returns the approximated pi.
public double computePI(int n) {
}
// This method takes a character stack of signs and updates the same stack
// so that it contains the result after one round of XOR operations.
public void evaluateSignsRec(CharStack signs) {
}
// This method reads a string and returns the string in the reversed order.
public String reverseStringRec(String s) {
}
// This method takes as parameters a reference to the head of a linked list, a
// position specified by n, and a key. It returns the number of occurrences
// of the key in the linked list beginning at the n-th node. If n = 0, it means
// you should search in the entire linked list. If n = 1, then you should skip
// the first node in the list.
public int numOccurrencesRec(LNode node, int n, int key) {
}
}
// Test driver for the RecursiveMethods class
// Do not make any changes to this file!
// Xiwei Wang
import java.util.Arrays;
public class TestRecursiveMethods {
static RecursiveMethods myMethods;
static int numTotalTests;
static int numPassedTests;
public static void main(String[] args) {
myMethods = new RecursiveMethods();
numPassedTests = 0;
numTotalTests = 0;
// Tests for computePI
int[] input1 = {1, 4, 7, 1000};
double[] expOutput1 = {4, 2.8952, 3.2837, 3.1406};
for (int i = 0; i < input1.length; i++) {
testComputePI(input1[i], expOutput1[i]);
}
// Tests for evaluateSignsRec
String[] input2 = {"++", "+-", "--+-", "--+++", "+--+++-+-+-"};
String[] expOutput2 = {"-", "+", "-++", "-+--", "+-+--+++++"};
for (int i = 0; i < input2.length; i++) {
testEvaluateSignsRec(input2[i], expOutput2[i]);
}
// Tests for reverseStringRec
String[] input3 = {"", "1", "123", "Hello, Data Structures!"};
String[] expOutput3 = {"", "1", "321", "!serutcurtS ataD ,olleH"};
for (int i = 0; i < input3.length; i++) {
testReverseStringRec(input3[i], expOutput3[i]);
}
// Tests for numOccurrencesRec
int[][] input4 = {{-999},
{20},
{20},
{45, 25, 73, 45, 19, 57, 45},
{45, 25, 73, 25, 19, 25, 43, 25},
{45, 25, 73, 25, 19, 25, 19, 45}};
int[] inN = {0, 0, 0, 0, 1, 4};
int[] inKey = {10, 10, 20, 45, 25, 19};
int[] expOutput4 = {0, 0, 1, 3, 4, 2};
for (int i = 0; i < input4.length; i++) {
testNumOccurrencesRec(input4[i], inN[i], inKey[i], expOutput4[i]);
}
System.out.println("Total test cases: " + numTotalTests + "\nCorrect: " + numPassedTests + "\nWrong: " + (numTotalTests - numPassedTests));
}
static void testComputePI(int input, double expOutput) {
double dReturn = -1;
String testResult = "[Failed]";
String eMsg = "N/A";
try {
dReturn = myMethods.computePI(input);
dReturn = Math.round(dReturn * 10000D) / 10000D;
if (dReturn == expOutput) {
numPassedTests++;
testResult = "[Passed]";
}
} catch (RuntimeException e) {
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
numTotalTests++;
String text = "Test " + numTotalTests + ": computePI(" + input + ") ==> " + testResult + "\n Expected: " + expOutput;
printMessage(eMsg, text, "" + dReturn);
}
static void testEvaluateSignsRec(String input, String expOutput) {
CharStack s = new CharStack(input.length());
String sReturn = "";
String testResult = "[Failed]";
String eMsg = "N/A";
try {
for (int i = input.length() - 1; i >= 0; i--) {
s.push(input.charAt(i));
}
myMethods.evaluateSignsRec(s);
sReturn = s.toString();
if (sReturn.equals(expOutput)) {
numPassedTests++;
testResult = "[Passed]";
}
} catch (RuntimeException e) {
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
numTotalTests++;
String text = "Test " + numTotalTests + ": evaluateSignsRec(\"" + input + "\" (from top to bottom)) ==> " + testResult + "\n Expected: \"" + expOutput + "\" (from top to bottom)";
printMessage(eMsg, text, "" + sReturn);
}
static void testReverseStringRec(String input, String expOutput) {
String sReturn = "";
String testResult = "[Failed]";
String eMsg = "N/A";
try {
sReturn = myMethods.reverseStringRec(input);
if (sReturn.equals(expOutput)) {
numPassedTests++;
testResult = "[Passed]";
}
} catch (RuntimeException e) {
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
numTotalTests++;
String text = "Test " + numTotalTests + ": reverseStringRec(\"" + input + "\") ==> " + testResult + "\n Expected: \"" + expOutput + "\"";
printMessage(eMsg, text, "" + sReturn);
}
static void testNumOccurrencesRec(int[] inArray, int inN, int inKey, int expOutput) {
int iReturn = -1;
String testResult = "[Failed]";
String eMsg = "N/A";
String list = Arrays.toString(inArray).replaceAll(", ", "->").replaceAll("-999", "NULL");
try {
// reverse the array
for (int i = 0; i < inArray.length / 2; i++) {
int tmp = inArray[i];
inArray[i] = inArray[inArray.length - 1 - i];
inArray[inArray.length - 1 - i] = tmp;
}
// build the list from the reversed array
LNode head = null;
for (int i = 0; i < inArray.length; i++) {
if (inArray[i] == -999) {
break;
}
LNode myNode = new LNode(inArray[i]);
myNode.setLink(head);
head = myNode;
}
iReturn = myMethods.numOccurrencesRec(head, inN, inKey);
if (iReturn == expOutput) {
numPassedTests++;
testResult = "[Passed]";
}
} catch (RuntimeException e) {
eMsg = "RuntimeException - \"" + e.getMessage() + "\"";
}
numTotalTests++;
String text = "Test " + numTotalTests + ": numOccurrencesRec(" + list + ", " + inN + ", " + inKey + ") ==> " + testResult + "\n Expected: " + expOutput;
printMessage(eMsg, text, "" + iReturn);
}
static void printMessage(String eMsg, String text, String ret) {
System.out.println(text);
if (eMsg.equals("N/A")) {
System.out.println(" Yours: " + ret + "\n");
} else {
System.out.println(" Yours: " + eMsg + "\n");
}
}
}