代写data编程、代写java程序语言、java代写编程调试

日期：2020-11-12 11:18

Overview

Reverse Polish Notation (or postfix notation) is a mathematical notation in which operators follow

operands. For example, the infix expression 2 + 4 is expressed as 2 4 + in postfix notation, and 1 + 4 *

3 is expressed as 1 4 3 * +. In this assignment, you are required to develop a reverse polish notation

calculator that can take an infix expression, convert it to postfix notation, 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-postfix parser, and a postfix

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 tests, meaning if your code may pass these tests,

but still fail the final marking if 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: Postfix

The second part of this assignment requires you to use the Collections to create an infix-to-postfix

converter and a postfix notation parser.

Marks:

infixToPostfix() 10

evaluate(Queue) 10

Converting from Infix to Postfix: Shunting-Yard Algorithm

We can use Dijkstra’s ’Shunting-Yard algorithm’ to parse infix expressions and output a reverse

polish notation. The shunting-yard algorithm is as follows:

? While there are tokens to be read:

1. Read a token.

2. If the token is a number: add it to the output queue.

3. If the token is an operator o1:

? While there is a token o2 at the top of the stack, and either:

? o1 is left-associative and has a precedence equal to that of o2

? o1 has precedence less than o2

pop o2 off the stack and push o2 onto the output queue

? push o1 onto the stack.

4. If the token is a left parenthesis: push it onto the stack.

5. If the token is a right parenthesis:

? Until the token at the top of the stack is a left parenthesis:

? Pop the top of the stack and add it to the output queue.

? Pop the top of the stack (the left parenthesis), but not onto the output

queue. If there are no tokens left on the stack but we did not find a left

parenthesis, the parentheses are unmatched (input error).

? When there are no more tokens to be read:

1. while there are tokens on the stack

? If the token is a parenthesis, we have an input error (unmatched

parentheses)

? Pop the stack onto the output queue.

2. Return the output queue.

Parsing a Postfix Expression

An algorithm to evaluate a postfix expression is as follows:

? While there are more input tokens:

o Read the next token.

o If the token is an operand:

? Push it onto the stack.

else the token is an operator O1:

? Pop the top element of the stack into a temporary variable E2.

? Pop the top element of the stack into a temporary variable E1.

? Evaluate the expression E1 O1 E2, and push the result onto the stack.

? When there are no more input tokens, there should be one item in the stack (if there is

more than one item in the stack, the input contained an error). Return the result.