CS2522 Algorithms and Data Structures

On successful completion the student will be able to:

• Discuss the concept and definition of abstract data types;
• Compare a variety of data structures and assess the circumstances when they should be used.
• Choose and implement appropriately a variety of basic data structures in a practical programming context.

Rules and submission procedures.

• Contain your source code and acknowledgment document showing the resources you have used. The source code should be:

Completely self-contained (i.e., your program can only refer to the normal JAVA libraries- do not use any data structure related built-in libraries such as ArrayList, LinkedList, Queue, or Stack).

Compile-able and runnable JAVA program under Windows. While creating this program, good programming practices should be followed (i.e., use meaningful classes, methods, and variables names as well as useful comments). 

• Include a JAR file of your JAVA program. You will lose points if you do not submit this JAR file.
• Contain a list of the screenshots showing that all requirements are implemented and working, i.e., showing that you tested your Infix-to-Postfix program.

Used Resources:

You must provide a list of the resources (books, web sites, and so on) that you have consulted to accomplish this assignment. These resources should be explicitly acknowledged in your submitted files/documents. If you do not have consulted resources, then state that explicitly as follows: The work included in this program is all my own work.

Task aim              

Developing an Abstract Data Type (ADT) and using it in an application by implementing and testing a JAVA program to convert infix expressions (the standard arithmetic expressions) into postfix expressions (usually used by computer programs).

Task rationale, details Infix and post notations are two types of notations for writing arithmetic and instructions: expressions. An infix notation is a well-known way for writing mathematical expressions (you are probably familiar with it since your primary school when you learned how to evaluate simple expressions such as addition, subtraction, multiplication, and division). It is called infix because each operator (e.g., +,-,*) appears in between its operands (values). 

Postfix notation is another way for writing the arithmetic expressions in which the operands appear before their operators (i.e., the operator is written after its operands). Unlike the infix notation, in the postfix notation, there are no precedence rules to learn, and parentheses are never required. Because of its simplicity, the postfix notation is usually used in some popular hand-held calculators to avoid complications encountered when multiple parentheses used in non-trivial infix expressions.

Consider the following example, 

Infix form: (P*Q) +(R/(S*(T^U))) 

Postfix form: PQ*RSTU^*/+ 

As you can see from the above example, the order of the operands is the same in infix and postfix. When we scan an expression for the first time, we can form the postfix by immediately passing any operands to the output. To handle the operators, we need storage to store them until it is time to pass them to the output. 

For this problem, you would think about whether you can use a queue ADT or a stack ADT as the needed storage. You need to implement your own chosen ADT using JAVA. While coding your chosen ADT (queue or stack), decide whether you would use arraylist or linkedlist to implement this ADT (i.e., queue or stack) and justify your decision. Whether you chose arraylist or linkedlist in building the stack or the queue, you need to provide the full implementation of the arraylist or linkedlist. For example, if you decided to use the queue ADT and decided to use the LinkedList to implement the queue, so you need to provide the full implementation (interface and classes) of the LinkedList. 

Note you are NOT allowed to use built-in data structure (Queue, ArrayList, LinkedList, or Stack ADT) libraries in JAVA.

Program Input: Your task is to write a main program that obtains an input line from users. Each input line contains one string which is a legal infix expression. The input infix expression is based on the following assumptions:

• It is a legal infix expression that contains at most 20 characters.
• It has only three operators: addition (+), multiplication (*) and division (/).
• It contains delimiter parentheses “(” and “)”.
• It has variables taken from the set {a, b, . . . ,z}.
• It contains no blank.

Program Output: For each input line (i.e., infix expression), your program should output a separate line containing the corresponding postfix expression.

Notes

It is important to know that the idea of this assignment is NOT just to create a user input for an infix operation and then outputs the postfix form given the infix form, BUT also to create and use ADT(s) (mentioned above). So, you MUST provide all the java interfaces and classes used in creating this abstract data type (this is the main point of the assignment). This means that you are NOT expected to use any built-in libraries for this abstract data type (e.g. you can NOT use import "java.util.Stack" NOR (java.util.*).

More clarification on the assignment, you can use input/output library from Java such as Scanner class and others. You can also use exception classes but you MUST import each of these classes individually. For example, in the case of file exceptions, you are expected to use import java.io.FileNotFoundException.

In short, you are NOT expected to use any built-in libraries for the abstract data type which you have to create and use (e.g. you can NOT use “import java.util.Stack"  ) but you are allowed to use other libraries such scanner or exceptions but you HAVE to import them individually.