Homework 7: Totally Not Pokemon game




COMP 2150
Homework 7: Stacks and Queues
(Max of 40/25 points)
1. (15 pts) Remember that Totally Not Pokemon game from near the beginning of the semester? You decide the
next step is to make a multiplayer, MMO-style version of it. Players will log into a central server, which will
maintain a queue of login requests so that not too many people are playing at the same time.
Unfortunately, the intern you hire to help you
write the MMO code never passed his data
structures class. (This makes you wonder why
you hired him in the first place, but that’s a
discussion for another time!) He insists that the
login queue should store the queue elements in
a linked list and should always fix the front of
the queue at the tail of the list, “because that’s easier.”
All your attempts at explaining why this is a Horrible Idea are met with much resistance. And due to strict labor
laws, you can’t just fire the intern without good reason. So you decide the best course of action is to implement
the intern’s plan, deploy it on your live server, watch your game subscriptions take a precipitous dive, blame the
intern for it, use that as a reason to let him go, and then sue him to recover your lost revenue. Because ‘MURICA.
(10 pts) Write a NaughtyLLQueue<E> class. Your class should implement a queue using a single linked
list. However, it should use the tail of the list as the front of the queue, meaning that when a dequeue is
performed, a traversal from the head node is required. Implement all four methods from the
interface (isEmpty, peek, enqueue, and dequeue) for this class. Calling dequeue or peek on an
empty queue should return
null, as our code did during lecture.
(5 pts) Write a client program that simulates the logging in of 100,000 players by using your “bad” queue
implementation as well as the “good” implementation that we wrote in class. Measure the time needed to
enqueue all 100,000 players, and then the time needed to remove them all from the queue.
Remember that you can use the built-in method
System.currentTimeMillis() to get the current
system time in milliseconds. Use this as a “stopwatch” – call
currentTimeMillis once to get the
starting time, execute the code you want to time, and then call
currentTimeMillis again to get the
ending time. The elapsed time is simply the difference between the start and end times.
Number of People: Up to 2. If you work with someone else, include both your name and your teammate’s name on
all source code files. Only one person needs to submit the final product to eCourseware, but include a note with the
submission that lists both of your names.
Feel free to ask me for help, or visit the Computer Science Learning Center
Due: Fri., Nov. 10 by 11:59 pm
Submission: Zip all your Java source files (you can zip the entire project folder if using an IDE) into a single file and
upload it to the proper folder in the eCourseware dropbox at
Coding Style: Use consistent indentation. Use standard Java naming conventions for
ClassNames, CONSTANT_NAMES. Include a reasonable amount of comments.
Grader: Rong Qi,
[email protected]. Questions about grading? Please contact her first!
2. (25 pts) As discussed in class, you can evaluate an infix expression by using two separate algorithms: one to
convert the infix expression into postfix, and one to evaluate the postfix expression. This requires two passes in
all. It’s possible to execute both algorithms at the same time, allowing you to evaluate an infix expression in a
single pass. Here’s how the combined algorithm works:
a. Maintain two stacks: one for
operands and one for operators/parentheses.
b. Scan the infix expression one token at a time, from left to right. Here a “token” is defined as an operand,
operator, or parentheses symbol.
i. If the token is an operand, push it onto the
operand stack.
ii. If the token is an operator or a parentheses symbol, handle it as described in the infix to postfix
conversion algorithm. Every time you pop a non-parentheses operator off the
operator stack,
also pop the top two elements off the
operand stack, perform the indicated operation, and push
the result back onto the
operand stack.
c. Once all tokens in the infix expression have been scanned, pop the remaining operators off the
while also modifying the operand stack as described in step b(ii).
d. The final result will be the top (and only) element left on the
operand stack at the end.
Write a program that uses the combined algorithm above to evaluate infix expressions entered by the user. The
program should support infix expressions involving any
double values (positive, negative, or zero) and any
combination of opening/closing parentheses () and these operators:
+ addition
– subtraction
* multiplication
/ division
^ exponentiation (e.g., 7^2 = 49) – keep in mind this one’s precedence is higher than * or /
You can use the built-in
java.util.Stack<E> class to keep track of your operands and operators. A few
assumptions you can make to simplify things a bit:
All tokens in the infix expression are separated by spaces.
The infix expression is well balanced with respect to parentheses, and properly formatted.
Regular parentheses are used for all levels of nesting (no curly braces or square brackets, ever).
The unary minus (to represent negative values) appears only in front of numbers, never in front of
parentheses. There is no space between a unary minus and its associated number.
Here’s an example of a running program; the underlined portions indicate user input.
Enter an infix expression with spaces between all tokens, X to exit:
1 + 2
Result: 3.0
Enter an infix expression with spaces between all tokens, X to exit:
1 + 2 * ( 10 – 4 )
Result: 13.0
Enter an infix expression with spaces between all tokens, X to exit:
( 1 + 2 ) * ( 10 – 4 )
Result: 18.0
Enter an infix expression with spaces between all tokens, X to exit:
( 1 + 2 ) * ( -4 + 10 ) ^ 2
Result: 108.0
Enter an infix expression with spaces between all tokens, X to exit:
2 * ( 1 – ( 4 + 3 ) )
Result: -12.0