Data Structures
Assignment 2A
Implementing a Polish Notation calculator in Java
Overview
Polish Notation (or prefix notation) is a mathematical notation in which operands follow operators. For example, the infix expression 2 + 4 is expressed as + 2 4 in prefix notation, and 1 + 4 * 3 is expressed as + 1 * 4 3. In this assignment, you are required to develop a polish notation calculator that can take an infix expression, convert it to a prefix expression, and then evaluate the expression to solve the equation.
Assumed Knowledge
Infix expressions are made up of operands and operators. Operands are the input: in the expression 1 + 2, the operands are 1 and 2. Operators are the action: for example, adding, subtracting, multiplying or dividing. The order operators are evaluated matters: choosing to do an addition before a multiplication gives a different result than doing the multiplication before the addition.
As an example, consider the expression 1 + 2 * 3. Evaluating the addition operator before the multiplication yields a different result:
Addition first:
1 + 2 * 3 == (1 + 2) * 3
== 3 * 3
== 9
Multiplication first:
1 + 2 * 3 == 1 + (2 * 3)
== 1 + 6
== 7
To avoid this ambiguity, operators are given precedence — when given a choice, operands are done in a specific order:
· Brackets (Parentheses)
· Exponents
· Division / Multiplication
· Addition / Subtraction
Thus, according to our precedence rules, the correct answer to our example above is 7 (multiplication before addition).
Implementation
There are two parts to this assignment. In part 1, you are required to implement several collections (Linked List, Stack and Queue). In part 2 you will implement an infix-to-prefix parser, and a Polish Notation (prefix) calculator. This assignment has tests to show how well your solution is working.
These tests are NOT 100% complete, meaning they will miss things, so you need to do your own testing as well. Final marking for the assignment will use additional more complete testing, meaning if your code passes the provided tests, you may not receive 100% for that section if it fails the marking tests (indicating your code is not fully functional).
Importing into eclipse
The Assignment has been provided as an eclipse project. You just need to import the project into an existing workspace. In the latest version of Eclipse, go File > Open Projects from File System and
open the directory of the project (the one with the src folder in it). For older versions, see Figure 1 for a visual guide. Make sure that your Java JDK has been set, as well as the two jar files that you need for junit to function. This can be found in Project > Properties > Java Build Path > Libraries. The jar files have been provided within the project; there is no need to download any other version and doing so may impact the testing environment. Cleaning the project may help some issues with your initial running of the project. This can be found in Project > Clean.
Part 1: Collections
In part 1, you will re-implement some of the Java Collections classes: LinkedList, Stack and Queue. There are three classes that require implementation: DSList.java, DSStack.java and DSQueue.java.
There is an «interface» provided for List, and «abstract classes» for both Queue and Stack. You will use the Linked List implementation as the basis for implementing Stack and Queue. For some methods there may be additional comments in the Javadoc.
DSList.java
Marks:
DSList() 0
DSList(Node) 2
DSList(DSList)
|
6
|
remove(int)
|
5
|
indexOf(Token)
|
3
|
get(int)
|
3
|
add(int, Token)
|
3
|
contains(Token)
|
3
|
remove(Token)
|
10
|
add(Token)
|
4
|
isEmpty()
|
3
|
size()
|
3
|
toString()
|
5
|
DSList will extend the List class defined in List.java. The implementation will be a double-linked list and must implement the abstract methods from List.java.
DSList should have one data member: public Node head. Others can be added if you require them. Implement the following methods in the List class:
· Constructor: implement a blank constructor which takes no parameters.
· Constructor: implement a constructor accepting one Node (containing a Token object). The constructor should set head to the given Node.
· Copy constructor: implement a copy constructor accepting a DSList object. The copy constructor should perform a deep copy of the DSList passed to the constructor: the new DSList should not contain references to the Node objects in the second DSList. (The two DSLists should be independent: changing the contents of Node objects in one DSList should not affect the other).
· public boolean add(Token obj): The add method should append the specified object to the end of the List.
· public boolean isEmpty()
· public int size()
· public String toString(): this should return a String created by concatenating each Nodes toString(). A single space: ‘ ’ should be inserted between each Nodes toString(). No trailing space should be inserted. For example, if the list contains 3 Node objects, an appropriate toString() return value could be ‘1 2 3’, but not ‘123’ or ‘1 2 3 ’ [note the trailing whitespace]. For further details, refer to the unit tests supplied with the assignment.
· public boolean equals(Object other): two DSList objects are equal if they contain the same Tokens in the same order.
· public int hashCode()
Implement the abstract methods in List.java. The Javadoc annotations in List.java explain what each methods should do.
· public boolean contains(Token object)
· public boolean remove(Token object)
· public Token remove(int index)
· public Token get(int index)
DSQueue.java
Marks:
DSQueue()
|
0
|
DSQueue(DSQueue)
|
2
|
offer(Token)
|
2
|
poll()
|
2
|
peek()
|
2
|
isEmpty()
|
0
|
toString()
|
0
|
The Queue implementation will extend the abstract class Queue.java. The base storage of the Queue
will be a List: you’ll use the implementation you did in DSList.java. Implement:
· Constructor that accepts no parameters. This constructor should initialize the internal storage of the Queue.
· Copy constructor that accepts a Queue. This constructor should do perform a deep copy of the second Queue.
Implement the abstract methods in Queue.java. The Javadoc annotations explain what the methods are required to do:
· public boolean offer(Token object)
· public Token poll()
· public Token peek()
DSStack.java
Marks:
DSStack()
|
0
|
DSStack(DSStack)
|
2
|
peek()
|
2
|
pop()
|
2
|
push()
|
2
|
empty()
|
2
|
toString()
|
0
|
The Stack implementation will extend the abstract class Stack.java. The base storage of the Stack will
be a List: you’ll use the implementation you did in DSList.java. Implement two constructors:
· Constructor that accepts no parameters. This constructor should initialize the internal storage of the Stack.
· Copy constructor that accepts a Stack. This constructor should do perform a deep copy of the second Stack. Implement the abstract methods in Stack.java. The Javadoc annotations explain what the methods are required to do.
Implement the following methods:
· public boolean empty()
· public Token peek()
· public Token push()
· public Token pop()
Part 2: Polish Notation
The second part of this assignment requires you to use the Collections to create an infix-to-prefix converter and a Polish (prefix) notation parser.
Marks:
infixToPrefix() 10
evaluatePrefix(Queue) 20
Converting
from Infix
to Prefix
A rough algorithm to convert from infix to prefix is as follows:
· While there are tokens to be read:
1. Read a token from the right hand end of the expression.
2. If the token is a number: add it to the output queue.
3. If the token is a parenthesis:
a. If the token is a right parenthesis, push it onto the stack.
b. If the token is a left parenthesis:
i. Until a right parenthesis is encountered on the top of the stack, pop from the stack onto the output.
ii. Remove the right parenthesis.
4. If the token is an operator (we will call that o1):
a. While there is a token (we will call this one o2) at the top of the stack with equal or higher precedence than o1: pop o2 off the stack and push o2 onto the output queue
b. push o1 onto the stack.
Hint:
Evaluate from the right side of the expression. The expression is given as a queue, where the left side of the expression is the front of the queue. Maybe reversing the queue would be a good idea?
Parsing
a Prefix Expression
Design an algorithm to parse the prefix expression.
Hints:
• Consider breaking the expression into smaller parts, consisting of exactly one operator and two operands.
• Helper methods are permissible.
• Make sure you’re comfortable evaluating expressions by hand first!
Infix to Prefix converter
Implement a method in Calculator.java called infixToPrefix(). The method should be public and should accept a DSQueue as its single parameter. The return type for the method must be a DSQueue.
Prefix parser
The final method to implement is the prefix expression parser. Create a method public double evaluatePrefix(DSQueue()) in Calculator.java. Develop an algorithm to parse the prefix expression and return the result as a double.
Marking
An automatic marking program has been included to test all the methods and algorithms that you implement. A modified version of the testing files will be used to assign your final marks. All values will be altered so you cannot hard code the answers the tests expect. JUnit, the library used to conduct the testing, relies on two JAR files being added to your build path:
• junit-4.12.jar
• hamcrest-core-1.3.jar
Both files have been provided along with your starting code.