need to be done java
1 CPS 350: Assignment 2 Due 11:55 pm, 2/14/2018 (100 pts) This is NOT a team project. No late submission will be accepte d 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 ADT Queue and uses Queue and Stack 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 a queue structure, called MyQueue clas s (2) To apply data structures to convert infix expressio n to postfix expression (3) 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. 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 needed. 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 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()”, “resize()”, “enq ueue()”, 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.
- “dequeue()” decreases the capacity to half of the current size if the number of elements is less than ¼ of the total capacity.
(3) Upon completing the “MyQueue.java”, you can tes t it by using the testing code below: 3 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 ; 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.
(4) 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). Your task is to implement “processPostfix()”. The relationships of these two functions and the one above “getInfixFromString()” are illustrated in figure 3: Figure 3: Functions relationships: from left to rig ht, each function’s output is the input for its right neighbor.
(5) To understand “infix2postfix()”, you can add the te sting 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()” f unction right before the line “ return postfix_queue;”: getInfgxFromStrgng() gnfgx2postfgx() processpostfgx() 4 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, + (6) 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. As we dequeue an item from the postfix queue, we ch eck if it is an operand or operator (i.e., +, -, or *). If it is an operand, push it onto an o perand-stack. If it is an operator (e.g., “*”), pop two items from the operand-stack, do the calculatio n, and then push the result onto the operand- stack. See below for illustration. postfixqueue: “5, 2, 3, *, +, 6, –, 18, +” After three dequeue(), operand-stack contain: 5, 2, 3 (left is bottom and right means top). 5 Afer 4 th dequeue(), we get *. So pop two operands from the operand-stack 3 and 2. The new value is 6. Push 6 onto the operand-stack. Now the operand-stack has: 5, 6 (top). After 5 th dequeue(), we get +. Pop two items from stack, 6, 5. Do the calculation. The new value is 11. Push 11 onto the operand-stack. Now the operand-stack contains: 11 Keep doing this while the postfix queue is NOT empt y. To get the final result, simply pop it from the operand-stack. 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. private String processPostfix (MyQueue postfix) { … MyStack operand_stack = new MyStack(); // declare a new empty stack int newValue = 0; while (!postfix.isEmpty()) { // get front item from postfix queue // if an operator , pop two items from stack and compute newValue bas ed on operator int item1 = Integer.parseInt(operand_stack.g etTopandPop().getData()); int item2 = … newValue = … // then push new value onto stack: operand_stack.pushNode(new StackNode(Integer. toString(newValue))); // if not an operator , then: operand_stack.pushNode(…); } // end of while // get final value from the stack and return it } // end of processPostfix (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 t he final result on the calculator’s screen. 3. Grading Notes Receive zero points if it has any compilation error Successfully complete the function “ isEmpty()” and “resize()” of MyQueue class (10%) Successfully complete the function “ enqueue()” of MyQueue class (30%) Successfully complete the function “ dequeue()” of MyQueue class (30%) Successfully complete the function “ processPostfix()” of MyStack class (30%) 6 3.1 Extra Points Receive 20 bonus points if you modify the implementation and make the calc ulator similar to the one on iphone (on the right, with more botto ms and more functions). 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.
