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 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.

2

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.

2.1 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.

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 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.

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 “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.

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 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:

4

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, +

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 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.