Lab 1

Exercise 1

In this program we will simulate a bank operation with customers being served by the tellers of the bank. The customers are arriving at random time points and they are put in a line, which in our case will be implemented as a fixed capacity queue. They wait there until a teller is available to serve them.

The simulation will decide how many customers were accepted, how many customers were served, how many customers were turned away because the queue was full, what was the average queue size during the operation hours and what was the average waiting time for the customers.

You are given the Java classes and, and the interface
You are asked to write a class named ArrayQueue  (or ListQueue) which implements the interface Queue given above.

public class ArrayQueue<Item> implements Queue<Item>

The class ArrayQueue (or ListQueue) should implement all the methods of the interface Queue. Those methods are used by the class Bank to perform the necessary operations. You can add more methods if you find it necessary.

- The class ArrayQueue would be nice to be generic, i.e. the object types to be stored in it will be specified by the client program. However, this is not a strict requirement. You should first try a type-specific implementation and then if you have time try to extend it using generics.

- A list implementation can be alternatively used. Both options are acceptable.

- The queue should have fixed size.
- It should use a fixed array size to store the objects. The capacity of the queue will be given a parameter to the constructor by the client program.
- You don't need and you should not modify the classes that you are given in order to make your program functional.
- Same input numbers it is not necessary that will produce the same output since the customer arrivals and service times are generated in random based on the average times specified by the user.

Execution example:
>java Bank 30 3 40

Customers accepted: 122
  Customers served: 92
 Customers waiting: 30
         Turnaways: 2
Average queue size: 15.511111
 Average wait time: 22.554348 minutes

Exercise 2

In this exercise you are asked to implement a program that can calculate arithmetic expressions with parentheses, arithmetic operators ("+, -, *, /") and powers ("^"). That means that your program should be able to get as input an expression of the form (2+5*3)^(2*3) and print out the result.

Your program should make the use of a stack as an auxiliary data structure to store your data. In the lecture you will see an algorithm that can calculate an arithmetic expression by using two stacks, one stack to store the numbers and one to store the operators. In this exercise you should come up with an algorithm that uses only one stack to achieve the same result.

Split your program in two stages. In the first stage convert the infix expression of the form (2+5*3)^(2*3) to a postfix (or reverse polish) expression of the form 253*+23*^ and print it. In the second stage calculate and print the result of the postfix expression. For your convenience you can assume that all the numbers of the expression are one character (digit) long integers.

You can find an algorithm and an example of converting an infix expression to a postfix expression here. The textbook (pages 144 and 146) also provides examples of evaluating a postfix expression and converting an infix expression to a postfix one using only the operators "*" and "+". You can use them as a starting point and extend them in order to use all 5 operators required by this assignment taking into consideration the operators' precedence characteristics.

For the needs of this program you should create an integer array stack (generic implementation will be considered a plus). We assume that we don't know the length of the expression from the beginning, so your stack should be able to dynamically shrink and expand while objects are pushed and popped from it. Start with a initial capacity of 3 and use the doubling and halving strategies that you were taught in the class to achieve so.

An array or a linked list can be alternatively implementated.

Execution example:
>java EvaluateExp (2+5*3)^(2*3)

Postfix expression: 253*+23*^
The result of the expression is: 24137569


A zip file of the form (e.g. containing the following:
  1. The Java source files. Do not include .class files or other executables.
  2. A README (.txt or .doc) document that contains:

To receive full credit make sure to follow the Java coding conventions in your programs. Your programs will be graded as explained in the syllabus of the class.
Instructions on how to write clear code you can find here.



[Acknowledgement to Vangelis Metsis for preparing the exercises]