Computer science homework
1 CPS 350: Assignment 2 Due 11:55 pm, 2/20/2017 (150 pts) No late submission will be accepted Receive 5 bonus points if turn in the complete work without errors at least one day before deadline Receive an F for this course if any academic dishonesty occurs 1. This assignment implements ADTs Stack and Queue for a calculator application. 2. In this project, we implement the “=” key for the c alculator by using postfix expression as figure 1 shows. After user enters the expression “5+3*12–2 06” 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 clas s (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 enter ing “+”, “5”. (d) the result of user hitting “=” again. (e) the result of user hitting “<”. (f) the result of user entering “+”, “2”, “*”, “5”. (g) t he result of user hitting “=” again. 2 From the demos in Figure 1(c) to (g), you can see t he calculator allows user to continue entering new expressions based on the previous calculation r esult. In other word, the output of “=” can be directly used as the input for subsequent expressio n in the next round. This feature offers user with extra convenience for multiple steps of calculation s. You don’t need to implement everything from scratch . The GUI part is already implemented. Now, you just need to focus on the “=” button implementa tion. 2.1 The provided Framework Download the “framework.zip” file and unzip it. The re are four source code files for this project:
(1) Calculator.java (2) MyStack.java (3) My Queue.java (4) application.css Again the “calculator.java” and “application.css” a re both completed that you do not need to write anything there. You need to work on the “MyStack.ja va” 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. 2.2 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 expres sion (i.e. extra operator at the end without an operand followed), it can automatically drop the ex tra 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 implemente d in the “getInfixFromString()” function. So no any extra coding is neede. However, you should b e 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 auto matic removal of the last invalid operator. 2.3 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 “e nqueue()” and “dequeue()” should have the ability to resize the array when it is necessar y. Here is the dynamic size changing policy:
- “enqueue()” increases the capacity to twice of th e current size if the array becomes full. 3 - “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 te st 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 bot tom of the “getInfixFromString()” function).
After you have finished the MyQueue class successfu lly, 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 implemente d. (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 “c omputeExp()” function of MyStack class, which involves five steps (read the comments in the sourc e 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 q ueue into a postfix queue and output it. The second function will use the postfix queue as the i nput and calculate the final result. So the relationships of these two functions and the one ab ove “getInfixFromString()” are illustrated in figure 3: 4 Figure 3: Functions relationships: from left to rig ht, 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 bot tom 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, + getInfixFromString() infix2postfix() processpostfix() 5 (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 fu nction 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, w hich is the return type for the function “processPostfix()”. If you have successfully implem ented 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. Y ou 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.
