CS 1311 Spring 2001 Assignment 12 REVISED2 This assignment is due Friday, April 6, 2001 at 9:00 a.m. You will need to get I/O Gadget running for this assignment. See the lecture notes. ###### ####### # # ### ##### ####### ###### # # # # # # # # # # # # # # # # # # # # # ###### ##### # # # ##### ##### # # # # # # # # # # # # # # # # # # # # # # # # # ####### # ### ##### ####### ###### 1. (15 pts) (Write a class LLNode which will hold a double called data and a reference to another LLNode called next. ------------------------------------------------------------------ NOTE: You must use these names exactly! data next <---+ | | Are we clear? All lower case. JUST LIKE THEY ARE SHOWN!!! ------------------------------------------------------------------ As a minimum it needs to have: A constructor which takes in a double and sets the data field equal to it AND sets next to null A toString method A main method used to test the LLNode class. 2. (40 pts) Write a class Stack using the LLNode class from problem 1. It should support or implement: public boolean isEmpty() public void push(double s) Hint: Implement like addToFront() public double pop() Hint: Implement like removeFirst() If the stack is empty return 0.0 public double peek() Just return the double from the first node don't change the list 3. (25 pts) Implement a stack-based RPN calculator (like an HP). Really. It's not as bad as it sounds and it might make clearer what you can do with a stack in a program. If you have no idea how an HP stack based calculator works there is a short explanation at the bottom The calculator might look something like this: (Sorry, didn't have enough time to code it for you but I put in comments so you can see the general idea.) class Calculator { // A calculator object will have its own stack Stack stk; // Constructor public Calculator() { // Create a stack object // Create a string reference // Use a loop (what kind?) // Prompt for and get a string from the user // This is a nice prompt: // // ?>> // If its a number (a double) push it onto stack // Else if its an operator // Process the operation // Note: If it's not a number or an operator we're // just ignoring it. // Print out the top of the stack // End of loop } // Constructor // We'll give you this method... public boolean isDouble(String s) { boolean retval = true; // If you want to know what this does take CS 1312 try { Double.parseDouble(s); } catch(NumberFormatException nfe) { retval = false; } finally { return retval; } } // What does this have to do? public boolean isOperator(String s) { // Yes, we know you know but you still have to prove it to // us by writing the method!!! } // Remember in the case of 3 + 4 // 3 and 4 are operands and the + sign is an operator // So call this method when you get an operator from the user. public void operate(String s) { double operand1; double operand2; //Get 2 operators from stack // REVISION REVISION REVISION REVISION REVISION REVISION operand2 = Double.parseDouble(stk.pop()); // REVISION operand1 = Double.parseDouble(stk.pop()); // REVISION // REVISION REVISION REVISION REVISION REVISION REVISION // Now depending on which operator it is // perform the operation and put the result where? } public static void main(String args[]) { All we need to start this baby up! Calculator c; c = new Calculator(); } } // Calculator Sordid Details ============== REVISION REVISION REVISION REVISION REVISION REVISION REVISION You should make your calculator exit if the user enters 'q' (without the quotes). REVISION REVISION REVISION REVISION REVISION REVISION REVISION You don't have to do any fancy error handling. We won't test with anything that will cause a problem like division by zero, etc. You may, of course, implement error handling if you wish. "Turn-in" Turn in to WebWork your .java and .class files for LLNode Stack Calculator You don't need to turn in IOGadget. This assignment will be autograded however no guarantee is made as to the availability of the autograder especially when the deadline approaches. Start (and finish) early. "Grading" Problem 1: 15 pts 2: 40 pts 3: 25 pts subtotal: 80 pts TA Evaluation: 10 pts (Comments, style and neatness, use of constants) 10 pts (Effective test mains for LLNode and Stack Appendix on stack-based calculators Actually all calculators are based on stacks its just that some are more obvious. The style used in HP calculators and in our little demo program is designed to make calculating complex expressions easily. Example: (2 + 4) x (3 + 6) ----------------- (8 + 7) Here is what we would enter (each line is assumed to be terminated with the enter key: 2 4 + 3 6 + * 8 7 + / Notice how we did not have to press any parentheses keys nor reenter or store any intermediate values. The stack did it all for us. This is what the screen would look like: ?>> 2 2.0 ?>> 4 4.0 ?>> + 6.0 ?>> 3 3.0 ?>> 6 6.0 ?>> + 9.0 ?>> * 54.0 ?>> 8 8.0 ?>> 7 7.0 ?>> + 15.0 ?>> / 3.6 ?>> 3. Extra Credit So you say that you're not doing to well and you would really love an opportunity to earn some extra credit??? We are here to help! Assume that the last two entries on the stack are labeled y and x with x being the last one entered (i.e. If you type 3 6 the y is 3 and the x is 6) Implement the following additional functionality: y^x (that is take y to the x power. You may assume that x is an integer) [3 points] If you make it work for values of x that are not integers you get an extra [3 points]. REVISION REVISION REVISION REVISION REVISION REVISION REVISION [Hint: Use logs!!!] REVISION REVISION REVISION REVISION REVISION REVISION REVISION x! That is x factorial (Do it recursively or iteratively) [3 points] REVISION REVISION REVISION REVISION REVISION REVISION REVISION [Hint: The operate method pops two values from the stack. That won't work for this. You'll have to figure out how to fix it!] REVISION REVISION REVISION REVISION REVISION REVISION REVISION swap x and y [3 points] A command (d) that toggles between showing just the top of the stack to showing all of the stack. In other words, the assigned implementation just shows the top value on the stack after each user entry. The d command will switch into a mode that will print out the whole stack after each operation or data entry. Order should be from most recent to oldest. [3 points]. So there is a possible 15 points of extra credit.