|
|
Comp201: Principles of Object-Oriented Programming I
|
The total extra credit assignment includes additional problems.
To see where we are going, download and run the demo (executable jar file--select "Open" when downloading): postfix.jar As you can see this is a really cheap postfix calculator: it does not support subtraction nor division. Nevertheless, it seems to calculate arithmetic expression in postfix notation correctly. It also displays the content of the stack and the accumulator that are internal to the calculator. What do we mean by an "postfix" expression? A binary operation is said to be in postfix notation if the operator (e.g. +) follows the two operands. There are also "infix" and "prefix" expressions. The following table shows an example of each form of notation.
Adding two numbers x, y together
Infix Notation x + y Prefix Notation + x y Postfix Notation x y +
Note that it is an Honor Code violation to attempt to decompile any of the demos in this assignment..
A postfix calculator, a.k.a. Reverse Polish Notation (RPN) calculator, is a calculator that computes arithmetic expressions in postfix notation. Internally it uses a stack, S, to store the operands in a postfix expression. It also has an accumulator, acc, to maintain the current input and to display the result of a computation. The RPN calculator does not maintain a "pending operation" as the infix calculator (see lab 12) does. Whenever a operation is entered, the RPN calculator immediately performs the operation. The following table illustrates how an RPN calculator works. Use the above postfix.jar demo to study the behaviors of the calculator yourself.
| Infix expression | Postfix Expression | Key Sequence | Internal Calculation | acc | S (grows to right) |
| 34 + 56 | 34 56 + | Enter 34 | acc = 34 | 34 | empty |
| Push | S.put(acc) | 34 | 34 | ||
| Enter 56 | acc = 56 | 56 | 34 | ||
| + | acc = S.get() + acc = 34 + 56 S.put(acc) |
90 | 90 | ||
| Clear | acc = 0; S.clear() |
0 | empty | ||
| 3 + ( 4 * 5) | 3 4 5 * + | Enter 3 | acc = 3 | 3 | empty |
| Push | S.put(acc ) | 3 | 3 | ||
| Enter 4 | acc = 4 | 4 | 3 | ||
| Push | S.put(acc ) | 4 | 3 4 | ||
| Enter 5 | acc = 5 | 5 | 3 4 | ||
| * | acc = S.get() * acc = 4 * 5 S.put(acc ) |
20 | 3 20 | ||
| + | acc = S.get() + S.get() = 3 + 20 S.put(acc ) |
23 | 23 | ||
| Clear | acc = 0; S.clear() |
0 | empty | ||
| (3 + 4) * 5 | 3 4 + 5 * | Enter 3 | acc = 3 | 3 | empty |
| Push | S.put(acc ) | 3 | 3 | ||
| Enter 4 | acc = 4 | 4 | 3 | ||
| + | acc = S.get() + acc = 3 + 4 S.put(acc ) |
7 | 7 | ||
| Enter 5 | acc = 5 | 5 | 7 | ||
| * | acc = S.get() + acc = 7 * 5 S.put(acc ) |
35 | 35 | ||
| Clear | acc = 0; S.clear() |
0 | empty | ||
| (3 + 4) * (5 + 6) | 3 4 + 5 6 + * | Enter 3 | acc = 3 | 3 | empty |
| Push | S.put(acc ) | 3 | 3 | ||
| Enter 4 | acc = 4 | 4 | 3 | ||
| + | acc = S.get() + acc = 3 + 4 S.put(acc ) |
7 | 7 | ||
| Enter 5 | acc = 5 | 5 | 7 | ||
| Push | S.put(acc ) | 5 | 7 5 | ||
| Enter 6 | acc = 6 | 6 | 7 5 | ||
| + | acc = S.get() + acc = 5 + 6 S.put(acc ) |
11 | 7 11 | ||
| * | acc = S.get() * S.get() = 11 *
7 S.put(acc ) |
77 | 77 | ||
| Clear | acc = 0; S.clear() |
0 | empty | ||
| 3 * (4 + 5) * 2 | 3 4 5 + * 2 * | Enter 3 | acc = 3 | 3 | empty |
| Push | S.put(acc ) | 3 | 3 | ||
| Enter 4 | acc = 4 | 4 | 3 | ||
| Push | S.put(acc ) | 4 | 3 4 | ||
| Enter 5 | acc = 5 | 5 | 3 4 | ||
| + | acc = S.get() + acc = 4 + 5 S.put(acc ) |
9 | 3 9 | ||
| * | acc = S.get() * S.get() = 9 * 3 S.put(acc ) |
27 | 27 | ||
| Enter 2 | acc = 2 | 2 | 27 | ||
| * | acc = S.get() * acc = 27 * 2 S.put(acc ) |
54 | 54 |
Your job is to design and implement a postfix calculator like the above demo with a simpler interface. This calculator has on the outside:
10 buttons labeled 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, respectively, to enter digit characters
one button labeled . to enter the decimal point
one button labeled +, to perform addition
one button labeled *, to perform multiplication
one button labeled "Push", to enter the display into the internal stack.
one button labeled C, to clear all entries in the calculator and reset the calculator to its pristine initial state
and a display text field for me to view the input and the result of my desired computation.
This calculator is to correctly compute any syntactically legal postfix expression. Entering any malformed postfix expression should result in an error. Click here to download and run the demo of the calculator you are going to produce: rpn.jar. The behaviors of this RPN calculator can be modeled as a finite state machine that is similar to the infix calculator done in lab 10. In fact, it has the same number of states as that infix calculator. Because the infix calculator and the postfix calculator differ in their internal representations, the actions performed in each state transition will differ.
1. 50 pts Describe the states and their transitions for your design. The examples shown in the above table should help you model the states and their behaviors. Instead of drawing the state transition diagram, use the table format illustrated by the following table for the start state instead. Please use MS Word and format your text nicely. Save your work in a file called "ReadMe.doc".
| start state | ||
| Event | Actions Performed | Next State |
| enterDigit(0) | display "0" | start state |
| enterDigit(d != 0) | display "d" | accum state |
| enterPoint() | display"0." | point state |
| etc. | etc. | etc. |
2. 50 pts Click here to download and save the source code of that you will need to use to implement your calculator: hw12.zip (includes the demo). Most of the files are the source code of the data structures you have learned in this semester: immutable list, mutable list, restrict access container. You need only complete the code for RNPMachine.java in the model package. RPNView.java in the view package is the view with the main method. You need not modify view at all. You must apply the state pattern to implement the state-dependent behaviors of RPNMachine. The behaviors of each state should reflect the behaviors you describe in part 1.
100 pts total.
When you have completed your homework, zip up the entire HW12/xtraCredit directory and submit the zipped file to your Comp 201 WEBCT account.
Be sure to include the additional problems!
Last Revised Thursday, 03-Jun-2010 09:50:22 CDT
©2008 Stephen Wong and Dung Nguyen