Java Assignment for CSS 143 comes with starter class file with psuedo code, just need to fill it in and make it meet requirements below.

Starter class file and desired output is copy and pasted at the bottom of assignment specifications.

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.

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.

Requirements Java file called RPN.java Data Structures Queue to store input Stack to evaluate input Methods: main() - test code double evaluateRPN(String input) - function to call with string boolean isOperator(String input) - evaluates if token is */+- String evaluateBinaryOperator(Double op1, String operator, Double op2) for example: evaluateBinaryOperator(2,+,2)=> 4. Javadoc headers for class and methods. No description of code, only what should happen to data Give examples of parameters passed & returned Comments Comment major blocks of code, not individual lines Comment WHY not WHAT. The code already shows WHAT. Testing 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. String String.valueOf(Double doubleInput) 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]

Starter class file:

========================RPN.java===================================

import java.util.*;

/** * TODO: * * @author * */ public class RPN {

/** * TODO: * * @param args */ public static void main(String[] args) { testRPN(); }

/** * Tests the RPN evaluator */ public static void testRPN() { String[] tests = { "2 2 +", "2 3 -", "4 5 *", "6 5 /", "1 2 3 4 5 6 7 8 9 + + + + + + + +", "5 2 2 * - 1 2 + /"}; double[] results = {4.0,-1,20,1.2,45, 0.3333333333333333};

for (int i = 0; i %s", tests[i])); double result = evaluateRPN(tests[i]); System.out.println(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 input - TODO * @return double - TODO */ public static double evaluateRPN(String input) { // Create queue, transfer input into it "2 3 +" -> [2 3 +]

// Print input

// Create new empty stack

// 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 +][2]=>[+][2 3]

// return last item in stack [][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 op1 - TODO: * @param operator - TODO: * @param op2 - TODO: * @return TODO: */ private static String evaluateBinaryOperator(Double op1, String operator, Double op2) { // Individual if/else or case switch to find operator + - * / // Return op1 }

}

==========================================================================

======================RPN Output.txt=========================================

Evaluating => 2 2 + [2, 2, +] [][4.0] Result => 4.0 Evaluating => 2 3 - [2, 3, -] [][-1.0] Result => -1.0 Evaluating => 4 5 * [4, 5, *] [][20.0] Result => 20.0 Evaluating => 6 5 / [6, 5, /] [][1.2] Result => 1.2 Evaluating => 1 2 3 4 5 6 7 8 9 + + + + + + + + [1, 2, 3, 4, 5, 6, 7, 8, 9, +, +, +, +, +, +, +, +] [+, +, +, +, +, +, +][1, 2, 3, 4, 5, 6, 7, 17.0] [+, +, +, +, +, +][1, 2, 3, 4, 5, 6, 24.0] [+, +, +, +, +][1, 2, 3, 4, 5, 30.0] [+, +, +, +][1, 2, 3, 4, 35.0] [+, +, +][1, 2, 3, 39.0] [+, +][1, 2, 42.0] [+][1, 44.0] [][45.0] Result => 45.0 Evaluating => 5 2 2 * - 1 2 + / [5, 2, 2, *, -, 1, 2, +, /] [-, 1, 2, +, /][5, 4.0] [1, 2, +, /][1.0] [/][1.0, 3.0] [][0.3333333333333333] Result => 0.3333333333333333 Congratulations - you passed the tests

=====================================================================

Prefix RPN 522*-1 2 / 54 2 Infix (S-(2*2))/(1+2)-5 22+12 (5-4) /(1+2) -54 +12 1 2+/ + 12 1 1 0.333333333 1 0.333333333 /3 3 0.333333333 Queue (front at left)) Stack (top at right)Operation Starting queue and stack Push operand 5 Push operand 2 Push operand 2 Pop 2 & 2 evaluate 2*2, push 4.0 Pop 5 & 4 evaluate 5-4, push 1.0 Push operand 1 Push operand 2 Pop 1 & 2 evaluate 1+2, push 3.0 [51 [5, 2] [5, 2, 2] [5, 4.0] t,D [0.33333333333333331 Pop 1 &3 evaluate 1/3, push.333333