Assignment
1. Purpose
This assignment implements ADTs Stack and Queue for a calculator application.
2. Description
In this project, we implement the "=" key for the calculator by using postfix expression as figure 1 shows. After user enters the expression "5+3*12-206" and hits the "=" key, it will display the arithmetic result on the screen "-165" (figure 1(b)). To achieve this goal, you need:
(1) To implement the MyStack class
(2) To implement a queue structure, called MyQueue class
(3) To apply the above two structures to convert infix expression to postfix expression
(4) To calculate the final result based on the postfix expression
(a) (b) (c)
(d) (e) (f) (g)
Figure 1: (a) user enters an arithmetic expression. (b) the calculation result after hitting "=". (c) after getting the result -165, user continues entering "+", "5". (d) the result of user hitting "=" again. (e) the result of user hitting "<". (f) the result of user entering "+", "2", "*", "5". (g) the result of user hitting "=" again.
From the demos in Figure 1(c) to (g), you can see the calculator allows user to continue entering new expressions based on the previous calculation result. In other word, the output of "=" can be directly used as the input for subsequent expression in the next round. This feature offers user with extra convenience for multiple steps of calculations.
You don't need to implement everything from scratch. The GUI part is already implemented. Now, you just need to focus on the "=" button implementation.
The provided Framework
Download the "framework.zip" file and unzip it. There are four source code files for this project:
(1) Calculator.java (2) MyStack.java (3) MyQueue.java (4) application.css
Again the "calculator.java" and "application.css" are both completed that you do not need to write anything there. You need to work on the "MyStack.java" and "MyQueue.java". When you run the framework for the first time, the "=" key just clears the calculator screen instead of giving any final result. So it is your turn to empower the "=" key with calculation ability and deliver the result to the screen.
Requirements
You are required to complete all the functions that have the comment "Implementation here: ..." in the "MyStack.java" and "MyQueue.java" files. The functions inside "MyQueue.java" are based on the Queue ADT that allows data to be stored in a "First-In-First-Out" manner. This container is needed to generate infix and postfix expressions.
In addition to the calculation ability for the "=" key as described above, we also require the "=" is robust enough that if user enters incomplete expression (i.e. extra operator at the end without an operand followed), it can automatically drop the extra operation. For example, if the entered expression is
"5 + 2 * 3 - 9 * 2 +"
the last "+" is not valid. So the calculator should ignore the last "+" during calculation. The good news is this validation check is already implemented in the "getInfixFromString()" function. So no any extra coding is neede. However, you should be aware of it. Because later on after you implement the MyQueue (as described below), you may encounter some testing cases with the missing last operator. So "No Upset" about the automatic removal of the last invalid operator.
Steps of implementation
(1) You should start programming from the "MyQueue.java" file, which has three important functions to complete "isEmpty()", "enqueue()", and "dequeue ()".
(2) The MyQueue class is implemented by using array, which requires an initial size. To let MyQueue dynamically grow or shrink its size, the "enqueue()" and "dequeue()" should have the ability to resize the array when it is necessary. Here is the dynamic size changing policy:
- "enqueue()" increases the capacity to twice of the current size if the array becomes full.
- "dequeue()" decreases the capacity to half of the current size if the number of elements is less than ¼ of the total capacity.
(3) After completing the "MyQueue.java", you can test it by using the testing code below:
MyQueue copy_infix_queue = new MyQueue();
while(!infix_queue.isEmpty())
{
String token = (String)infix_queue.dequeue(); System.out.println(token); copy_infix_queue.enqueue(token);
}
infix_queue = copy_infix_queue;
You need to copy and paste the above piece of code to the "MyStack.java" at line 285 if you have not done any code in this file yet (at the bottom of the "getInfixFromString()" function). After you have finished the MyQueue class successfully, this piece of testing code will print out all the "operand" and "operator" separately at the console. For example, in figure 2, after entering "95+23*5", then hit the "=" key. There are 5 tokens extracted "95", "+", "23", "*", "5". They are stored in an infix queue. This token extraction task is performed by the "getInfixFromString()", which is already implemented.
(a) (b)
Figure 2: testing result: (a) what user has entered in the calculator (b) An infix expression output to the console after hitting "=" key.
(5) After user hits the "=" key, it will trigger the "computeExp()" function of MyStack class, which involves five steps (read the comments in the source code). Three out of the five steps are already completed. The only two remaining steps are encapsulated in the two functions: "infix2postfix()" and "processPostfix()". They are the two major tasks for you to accomplish. The first function aims to convert an input infix queue into a postfix queue and output it. The second function will use the postfix queue as the input and calculate the final result. So the relationships of these two functions and the one above "getInfixFromString()" are illustrated in figure 3:
Figure 3: Functions relationships: from left to right, each function's output is the input for its right neighbor.
(6) After you have finished implementing "infix2postfix()", you can add the testing code below. Similar to the way you tested "getInfixFromString()" in step (3), you need to copy and paste the following code to the "MyStack.java" at the bottom of "infix2postfix()" function right before the line "return postfix_queue;":
MyQueue copy_postfix_queue = new MyQueue();
while(!postfix_queue.isEmpty())
{
String token = (String) postfix_queue.dequeue(); System.out.println(token); copy_postfix_queue.enqueue(token);
}
postfix_queue = copy_postfix_queue;
Run the code. Then you should be able to see a list of tokens are output to the console in a postfix order as Figure 4 shows.
Figure 4: testing result: (a) what user has entered in the calculator (b) A postfix expression output to the console after hitting "=" key.
Below are some additional examples about infix and postfix conversion result
|
Infix Expression
|
Postfix Expression
|
|
5+2*3-6+18
|
5, 2, 3, *, +, 6, -, 18, +
|
|
-5*2+95-5
|
-5, 2, *, 95, +, 5, -
|
|
52*3-9+17
|
52, 3, *, 9, -, 17, +
|
|
2-6-5+10*3+4
|
2, 6, -, 5, -, 10, 3, *, +, 4, +
|
(7) For the "processPostfix()" function, it calculates the final result according to the input postfix queue. Here you need to create a stack variable of MyStack to store all the operands.
Attentions: (a) when you push a node into MyStack, you should call the "pushNode()" function instead of "push()". This is because, the "push()" is a special function for the calculator use only for keyboard input. But this function can NOT be used as the general push action for stack. So I put a general push function, called "pushNode()" in the class. It is already implemented. You just need to use it. (b) After you compute the final value from the postfix expression, you need to convert it into a String, which is the return type for the function "processPostfix()". If you have successfully implemented this function, you should be able see the final result on the calculator's screen.
3. Grading Notes
• Receive zero points if it has any compilation error
• Successfully complete the function "isEmpty()"of MyQueue class (10%)
• Successfully complete the function "enqueue()" of MyQueue class (15%)
• Successfully complete the function "dequeue()" of MyQueue class (15%)
• Successfully complete the function "infix2postfix()" of MyStack class (30%)
• Successfully complete the function "processPostfix()" of MyStack class (30%)
4. Submission
Your project should be submitted through ISIDORE. You just need to turn in your updated version of the source codes "MyStack.java" and "MyQueue.java", which can be zipped into a single folder.
Attachment:- Attachments.rar