Programming Project #3 B – Stacks & Queues
(Originally by Prof. George Hu)
Last Updated 2/4/2019 1:48 PM
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 you’ve ever seen a computer or financial professional with a very basic calculator and a single line display it’s 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. There’s some good basic code there, but instead of using recursion, we’re going to use the stack. Recursion actually uses a stack as well, but it’s the same stack that executes your program. We’re 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. It’s 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 pseudo- data because I don’t want you to write code, I want you to write about how you’re 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 haven’t used before. If you google for how to do this homework I’ll 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 can’t 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 book’s example prefix evaluator has code to evaluate an expression. You may adapt this, but it’s 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 won’t 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]
