Homework 6

due: Thursday April 10 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]

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 - 5 would be written as 3 5 - in postfix.
The infix expression 3 + 5 * 7 would be written as 3 5 7 * + in postfix.
The infix expression 47 5 7 + * 4 would 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 an arithmetic expression 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.split to split the input string into an array of tokens, i.e. input.split(" ") to split the input at the spaces.
Integer.valueOf to convert a String to an integer.

You can use any utility you prefer to represent the stack of integers used during the computation.

Note: You do not need to do any error checking. You can assume that the input expression is well-formed.

Part 2: Reflection [5 points]

We are just past the halfway point in the semester, so we are checking in to see how the course is going, and if there is anything we 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/puBiQaSXw6jYdAoP9

The screenshot should look something like this (without the "example" text):

Submission

Upload Calculator.java and the image confirming your reflection submission to Gradescope. Remember to check the style of your code, and add your name to a comment at the top of your file!