Lab07 Stacks

CSC220 Lab07
Stacks
The goal of this week’s lab is:
1. Practice using stacks
2. Practice using Javadoc
3. Learn about the importance of debugging
Things you must do:
1. There are many details in this assignment. Make sure you read the whole thing
carefully before writing any code and closely follow this instruction.
2. You must complete your assignment individually.
3. Always remember Java is case sensitive.
4. Your file names, class names, package name, and method signatures must
match exactly as they are specified here.
Things you must not do:
1. You must not change the file names, class names, package names.
2. You must not change the signature of any of these methods (name, parameters,
…).
Important Note: There are many details involved. We are providing test cases
here for you but you are encouraged to write your own tests as well. You can
make the assumption that the given expression is valid and you don’t need to
worry about receiving an invalid expression as the input.
Part 0
• Create a new Java project and call it Lab07.
• Create a package inside your project and call it lab07.
• Download the Lab07-Assignment07 ZIP folder from Blackboard (google drive link).
Copy and paste the following files into your new lab07 package:
● Postfixer.java. You will be working on developing methods for this class.
● StringSplitter.java. This class breaks up a string into a sequence of
tokens using both whitespace and a list of special characters. The special
characters in this case are used to tokenize an arithmetic expression. For
example, the expression: “2*3.8/(4.95-7.8)” would be tokenized as [“2”,
“*”, “3.8”, “/”, “(“, “4.95”, “-”, “7.8”, “)”] even though it has no whitespace
to separate these tokens. This task is accomplished using a Queue to
hold the tokenized representation of an input string.
Part 1 – Problem Description
For this lab, you are asked to write a method (as part of Postfixer class) that
accepts an infix expression (3+5 as opposed to 3 5 +), use the StringSplitter
class to tokenize that expression and then evaluate it. To accomplish this task, you
are asked to use a variation of a famous algorithm known as the shunting-yard
algorithm (invented by Edsger Dijkstra). This algorithm uses two stacks to save the
intermediate results. One stack stores the operands (values being operated on) and
the other stack stores the operators (+/-*^). The basic idea is that we use the stacks
to store values (operands or operators) inside them till we are ready to evaluate the
expression. How are we going to do this? We will see that in the next section.
Part 2 – Helper methods
In this section, we consider ways we can break down a larger (harder) problem into
smaller pieces. The Postfixer class contains method stubs with Javadoc comments.
Review and implement. Be sure to test each individual method to confirm it works as
intended. We are now ready to turn to the shunting-yard algorithm. You must follow
the algorithm given in Part 4 exactly!
Part 3 – infixEvaluator method
You are required to implement the following method:
public static double infixEvaluator(String line)
This function first needs to tokenize the input expression (in the form of a String and
stored in input variable “line”). You can tokenize the input expression by creating an
object of StringSplitter and passing it the String as follows. StringSplitter uses a queue
to accomplish the tokenization (see the class for details).
StringSplitter data = new StringSplitter(line);
Next, create your two stacks. Remember one will contain the operators and the other
one will include the operands. Define them as follows:
Stack<String> operators = new Stack<String>();
Stack<Double> operands = new Stack<Double>();
Before we continue further in this method, it will be helpful to consider helper methods
we might need (which will make our job easier :-).
Part 4 – Shunting-yard algorithm
Here is the pseudo-code of the algorithm you have been asked to implement:
1. Scan the input string (infix notation) from left to right. One pass is sufficient, take
one token at a time. Each type of token is treated differently:
1.1. number: push it onto the operand stack.
1.2. a left parenthesis: push it onto the operator stack.
1.3. a right parenthesis:
1.3.1. while the thing on top of the operator stack is not a left parenthesis
1.3.1.1. pop an operator from the operator stack, pop two operands
from the operand stack, apply the operator to the operands, in
the correct order, push the result onto the operand stack.
1.3.2. pop the left parenthesis from the operator stack and discard it
1.4. an operator (call it current operator):
1.4.1. while the operator stack is not empty, and the top thing on the operator
stack has the same or greater precedence as the current operator [“(“ should
have the smallest precedence as is suggested in the code comments]
1.4.1.1. pop an operator from the operator stack, pop two operands from
the operand stack, apply the operator to the operands, in the correct
order, push the result onto the operand stack
1.4.2. push the current operator onto the operator stack
2. (After you have traversed the entire StringSplitter queue) While the operator stack is
not empty:
2.1. pop an operator from the operator stack, pop two operands from the operand
stack, apply the operator to the operands, in the correct order, push the
result onto the operand stack
3. At this point the operator stack MUST be empty, and the operand stack MUST have
a single value, which is the final result.
4. pop that value and return it.
Try to follow the algorithm on paper using the expression: 100 * ( 2 + 12 ) / 14.
The result should be 100.
----> Top of stack ---->
Operators = [ ]
Operands = [ 100 ]
PSEUDOCODE:
The operators we want you to be able to handle are:
+, -, *, /, ^.
Keep in mind the following points:
1. How can you access each token from the expression? Remember we have tokenized it using
the queue StringSplitter. Look at different methods in this class and see how you
can get a token from the StringSplitter object you defined in the previous section
(i.e., data).
2. How can you check whether there are any tokens left in the queue?
3. You need to inspect each token to see whether it is a number, an operator or a parenthesis.
How can you do that?
a. There are many ways to do this. However, an easy way is to first check whether the
token is a parenthesis, then check whether it is an operator, if
none of these two are true, then it is an operand. ParseDouble()
from Double class can come handy to convert an operand token
to a double value.
b. An alternative is to write a helper function to figure out whether a token is an
operand, an operator, or parenthesis.
3. Whenever you need to apply an operator, make sure you are careful about the order of
operands (see Javadoc in the evaluate helper method). This requires a little
bit of thought to get it right.
Part 5 – Test your code
After you are done implementing your infixEvaluator, you need to test it, as always! We
have provided different test scenarios for you in the main method.
Run your code, if you see any red text that says “test failed”, you need to debug
your code. How to debug your code?
1. Use the Eclipse debugger you learned about during the first lab
(Refresher from YouTube: https://www.youtube.com/watch?v=9gAjIQc4bPU)
2. Think about writing additional helper methods that help you inspect the status of
your stacks, etc.
3. Go back to your pen/paper example and follow your code to see if indeed it does
what it is supposed to.
4. Many other ways…
Don’t forget: lab and assignment are due Tuesday night @ 11:59pm!