Programming Project #3 B Stacks & Queues When I think of stacks, the first and only thing that comes to mind is a computer. Every computer you have ever seen, touched, worn, carried in your pocket, or programmed runs the same way with a stack. Every procedure call involves pushing all the formal parameters, and every procedure starts its execution by referencing those parameters on the stack again. When you declare a local it allocates stack space for it. One very simple type of computer is an RPN calculator and you will implement it. RPN stands for Reverse Polish Notation and quite simply it means that operators come after the operands. If youve ever seen a computer or financial professional with a very basic calculator and a single line display its probably an HP calculator which uses RPN. Instead of typing in 1 + 1 = as you would in a normal calculator, you instead type 1 1 +. The advantage comes when you have very complex expressions because no parenthesis are required. I still own and use an HP 11C (scientific) and 16C (programming). The Building Java Programs book has a good explanation of how to implement a prefix calculator using recursion in section 12.6. Theres some good basic code there, but instead of using recursion, were going to use the stack. Recursion actually uses a stack as well, but its the same stack that executes your program. Were going to setup a Java Collections Stack object to manage our RPN calculations. RPN... parenthesis free calculations Here's how RPN, Infix (the normal way), and Prefix (see the book) are evaluated. Note that only the infix method requires parenthesis. Its a matter of preference, but many consider RPN evaluation the simplest to code as well as perform on a calculator. RPN Evaluation Algorithm We are going to use stacks and queues to solve this problem. First, we convert the string into a queue. This allows us to easily get each item. Each item (called a token) will be removed from the front of the queue. The algorithm to evaluate RPN is simple: Operator (* / + -): pop two operands off the stack, evaluate, push result back Operand (anything else): push onto the stack Example Queue and Stack The sample expression is evaluated below, showing the queue and stack contents. Pseudo-Data Data, not Code Start by using these examples to write pseudocode. Perhaps it should really be called pseudodata because I dont want you to write code, I want you to write about how youre transforming data in English. For example, a very high-level pseudocode might be (Data structures are listed as [queue][stack]): Remove String input (2 3 +) put into queue ([2, 3, +]) For each queue item If operator (+-*/), evaluate it using stack ([+] [2, 3] => [][5]) Else operand, push it onto stack ([2, 3, +][] => [3, +][2]) Last item in stack is the result Now try to refine the pseudocode until you have something with enough detail that someone else can implement it. Requirements Java file called RPN.java Data Structures o Queue to store input o Stack to evaluate input Methods: o main() - test code o double evaluateRPN(String input) - function to call with string o boolean isOperator(String input) - evaluates if token is */+- o String evaluateBinaryOperator(Double op1, String operator, Double op2) for example: evaluateBinaryOperator(2,+,2)=> 4. Javadoc headers for class and methods. o No description of code, only what should happen to data o Give examples of parameters passed & returned Comments o Comment major blocks of code, not individual lines o Comment WHY not WHAT. The code already shows WHAT. Testing o To facilitate testing, I am providing a testRPN() method which will call your evaluateRPN() method and test it with several samples. Verify each test works in order. This set of tests is not enough to guarantee your code is bug free. I am providing an output file which you must match exactly, including spacing, and submit the diffchecker.com screenshot showing the files are identical. Useful Coding Tips You may find these operations helpful to convert between doubles and strings. These are the only fancy functions you may use which we havent used before. If you google for how to do this homework Ill know by what functions you used. o String String.valueOf(Double doubleInput) o Double Double.parseDouble(String stringInput) Queue is a Java Interface, whereas Stack is a regular Java Class. Remember that you cant instantiate a new Queue, but rather you must create an object which implements the Queue interface. When implementing isOperator, there are very long but straightforward ways of doingit, and there is a short and clever way of doing it. The books example prefix evaluator has code to evaluate an expression. You may adapt this, but its not exactly the same. Pay attention to data type conversions. Output To aid in debugging and reinforce the examples, output the following. After transferring the input to a queue, print it on its own line (once per expression) After each evaluation of an operator, print both the queue and stack together on one line (once per operator) Your output for the given example should look exactly like this. Note your output wont show pushing each operand for brevity. [5, 2, 2, *, -, 1, 2, +, /] [-, 1, 2, +, /][5, 4.0] [1, 2, +, /][1.0] [/][1.0, 3.0] [][0.3333333333333333]

import java.util.*; TODO: * @author public class RPN TODO: * @param args public static void main(String[] args)f testRPN) Tests the RPN evaluator public static void testRPN) String tests "1 2 3 4567 89+ + + ", "5 2 2 * - 1 2+ /"; double [] results4.0,-1,20,1.2,45, 0.3333333333333333; for (inti 0; i %s", tests [i])); double resultevaluateRPN (tests [i]); System . out . print1n(String . format ( "Result %s", result)); if (result results [i]) System . out.println(string. format ("Error on test %s expected %s, received %s", tests [i], results[i], evaluateRPN (tests[i]))); return System.out.println("Congratulations you passed the tests"); TODO: * @param inputTOD0 return double - TODO public static double evaluateRPN(String input)f // Create queue, transfer input into it "2 3[2 3 +] /1 Print input // Create new empty stack /I Pop off each item in the queue and evaluate it // if operator such as *' - pop two operands, evaluate, push result: Queue [+] Stack [2 3] [][5] // else operands such as "5" just need to be pushed [3 (21->+] 12 3] // return last item in stack [1 [5] TODO: TODO: * @param input - TODO return double - TODO public static double evaluateRPN(String input)f // Create queue, transfer input into it "2 3 "->[2 3 /1 Print input // Create new empty stack /I Pop off each item in the queue and evaluate it // if operator such as '+' - pop two operands, evaluate, push result: Queue [+] Stack [2 3] -> [][5] // else operands such as "5" just need to be pushed [3 (21->+] 12 3] // return last item in stack [1 [5] TODO: @param input - TODO: * @return boolean - TODO private static boolean isOperator (String input) / Check if the String is one of the * / characters // Either compare against each character individually or use String.contains TODO: evaluateBinaryOperator(2, "+", 3)-> "5" * @param oplTOD0: * @param operator - TODO: * @param op2TOD0: *@return TODO: private static String evaluateBinaryOperator (Double op1, String operator, Double op2) f /I Individual if/else or case switch to find operator -* / // Return op1 soperator>