Homework 6
due: Friday November 1st at 11:59pm (submit on Gradescope here).
Goals:
- Implement a calculator using a stack.
- Reflect on how the course is going so far.
Part 1: implement a calculator [5 points]
Please complete the calculate method in the Calculator.java file (download the template here). The calculator we will develop will use a type of notation called postfix notation to keep track of how the operations should be ordered. This is different than the notation we usually use to represent the order of a sequence of operations (called infix notation).
For example, when we want to calculate "3 minus 5" (which is -2), we usually write this as 3 - 5 (infix notation). With infix notation, the operator - is in between the two operands (3 and 5). In postfix notation, the operator is written after the operands. For example,
- The infix expression
3 - 5would be written as 3 5 -in postfix. - The infix expression
3 + 5 * 7would be written as 3 5 7 * +in postfix. - The infix expression
47 5 7 + * 4would be written as 47 5 7 + 4 * -in postfix.
The main advantage of postfix notation is that we can do the calculation as we read the operations from left to right. Using a stack of numbers, we can do postfix computations as follows:
- If the next token is a number, push it to the stack.
- If the next token is an operation (
*, /, +, -), remove the top two tokens from the stack (which are numbers), perform the computation, and push the result to the stack.
Here is the calculation of 47 5 7 + 4 * -. The current token being processed is on the left, and the resulting stack after processing the operation is also shown (the leftmost item is at the top of the stack).
| Step | Token | Stack | |
|---|---|---|---|
| 1 Â Â Â Â | 47 |
[47] |
number, push to stack |
| 2 Â Â Â Â | 5 |
[5, 47] |
number, push to stack |
| 3 Â Â Â Â | 7 |
[7, 5, 47] |
number, push to stack |
| 4 Â Â Â Â | + |
[12, 47] |
operator, calculate 5 + 7 and push 12 to stack |
| 5 Â Â Â Â | 4 |
[4, 12, 47] |
number, push to stack |
| 6 Â Â Â Â | * |
[48, 47] |
operator, calculate 12 * 4 and push 48 to stack |
| 7 Â Â Â Â | - |
[-1] |
operator, calculate 47 - 48 and push -1 to stack |
The final result is -1, which is the last item remaining on the stack.
Notice that with postfix notation, the first number popped from the stack (when performing an operation) is on the right of the operand, and the second number popped from the stack is on the left of the operand.
Complete the calculate method to take a String representing the sequence of operations described in postfix notation, and return the result of the calculation. You can assume that we will only work with integers in this assignment and that the operators will only be *, /, + or -.
Built-in methods you will probably need:
String.splitto split the inputstring into tokens, i.e. input.split(" ")to split the inputat the spaces.Integer.valueOfto convert a Stringto an integer.
You can use any utility you prefer to represent the stack of integers used during the computation.
Part 2: reflection [5 points]
We are just past the halfway point in the semester, so I would like to check in and see how the course is going, and if there is anything I can do to support you and help you learn the course material.
Please complete the reflection in the form linked below and save a screenshot of the submission confirmation page to upload to Gradescope. Your submission will be completely anonymous. There is no requirement on the file name or the image format.
https://forms.gle/BF37CJxuWBVhzP3t6
The screenshot should look something like this (without the "example" text):
Submission
Please upload Calculator.java and the image confirming your reflection submission to Gradescope and remember to check the style of your code.