# 算法代写 | 调度场算法 Shunting-Yard Algorithm Assignment

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

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

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 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()
DSQueue(DSQueue)
offer(Token)
poll()
```
```peek()
isEmpty()
toString()
```

0 2 2 2 2 0 0

The Queue implementation will will be a List: you’ll use the implementation you did in DSList.java.

extend the abstract class Queue.java. The base storage of the Queue

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

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()

Implement:

DSStack() 0 DSStack(DSStack) 2 peek() 2 pop() 2 push() 2 empty() 2 toString() 0

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

E-mail: [email protected]  微信:itcsdx