OverviewReverse Polish Notation (or postfix notation) is a mathematical notation in which operators followoperands. 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 notationcalculator that can take an infix expression, convert it to postfix notation, and then evaluate theexpression to solve the equation.Assumed KnowledgeInfix expressions are made up of operands and operators. Operands are the input: in the expression1 + 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 additionbefore 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 themultiplication yields a different result:Addition first:1 + 2 * 3 == (1 + 2) * 3== 3 * 3== 9Multiplication first:1 + 2 * 3 == 1 + (2 * 3)== 1 + 6== 7To avoid this ambiguity, operators are given precedence — when given a choice, operands are donein a specific order: Brackets (Parentheses) Exponents Division / Multiplication Addition / SubtractionThus, according to our precedence rules, the correct answer to our example above is 7(multiplication before addition).ImplementationThere 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 postfixcalculator. This assignment has tests to show how well your solution is working. These tests are NOT100% complete, meaning they will miss things, so you need to do your own testing as well. Finalmarking 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 eclipseThe Assignment has been provided as an eclipse project. You just need to import the project into anexisting 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 1for a visual guide. Make sure that your Java JDK has been set, as well as the two jar files that youneed for junit to function. This can be found in Project > Properties > Java Build Path > Libraries. Thejar files have been provided within the project; there is no need to download any other version anddoing so may impact the testing environment. Cleaning the project may help some issues with yourinitial running of the project. This can be found in Project > Clean.Part 1: CollectionsIn 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 willuse the Linked List implementation as the basis for implementing Stack and Queue. For somemethods there may be additional comments in the Javadoc.DSList.javaMarks:DSList() 0DSList(Node) 2DSList(DSList) 6remove(int) 5indexOf(Token) 3get(int) 3add(int, Token) 3contains(Token) 3remove(Token) 10add(Token) 4isEmpty() 3size() 3toString() 5DSList will extend the List class defined in List.java. The implementation will be a double-linked listand 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 copyconstructor should perform a deep copy of the DSList passed to the constructor: the newDSList should not contain references to the Node objects in the second DSList. (The twoDSLists should be independent: changing the contents of Node objects in one DSList shouldnot affect the other). public boolean add(Token obj): The add method should append the specifiedobject to the end of the List. public boolean isEmpty() public int size() public String toString(): this should return a String created by concatenating eachNodes toString(). A single space: ‘ ’ should be inserted between each Nodes toString(). Notrailing space should be inserted. For example, if the list contains 3 Node objects, anappropriate toString() return value could be ‘1 2 3’, but not ‘123’ or ‘1 2 3 ’ [notethe trailing whitespace]. For further details, refer to the unit tests supplied with theassignment. public boolean equals(Object other): two DSList objects are equal if they containthe same Tokens in the same order. public int hashCode()Implement the abstract methods in List.java. The Javadoc annotations in List.java explain what eachmethods should do. public boolean contains(Token object) public boolean remove(Token object) public Token remove(int index) public Token get(int index)DSQueue.javaMarks:DSQueue() 0DSQueue(DSQueue) 2offer(Token) 2poll() 2peek() 2isEmpty() 0toString() 0The Queue implementation will extend the abstract class Queue.java. The base storage of the Queuewill be a List: you’ll use the implementation you did in DSList.java.Implement: Constructor that accepts no parameters. This constructor should initialize the internalstorage of the Queue. Copy constructor that accepts a Queue. This constructor should do perform a deep copy ofthe second Queue.Implement the abstract methods in Queue.java. The Javadoc annotations explain what the methodsare required to do: public boolean offer(Token object) public Token poll() public Token peek()DSStack.javaMarks:DSStack() 0DSStack(DSStack) 2peek() 2pop() 2push() 2empty() 2toString() 0The Stack implementation will extend the abstract class Stack.java. The base storage of the Stack willbe 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 internalstorage of the Stack. Copy constructor that accepts a Stack. This constructor should do perform a deep copyof the second Stack. Implement the abstract methods in Stack.java. The Javadoc annotationsexplain 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: PostfixThe second part of this assignment requires you to use the Collections to create an infix-to-postfixconverter and a postfix notation parser.Marks:infixToPostfix() 10evaluate(Queue) 10Converting from Infix to Postfix: Shunting-Yard AlgorithmWe can use Dijkstra’s ’Shunting-Yard algorithm’ to parse infix expressions and output a reversepolish 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 o2pop 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 outputqueue. If there are no tokens left on the stack but we did not find a leftparenthesis, 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 (unmatchedparentheses) Pop the stack onto the output queue.2. Return the output queue.Parsing a Postfix ExpressionAn 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 ismore than one item in the stack, the input contained an error). Return the result.本团队核心人员组成主要包括BAT一线工程师，精通德英语！我们主要业务范围是代做编程大作业、课程设计等等。我们的方向领域：window编程 数值算法 AI人工智能 金融统计 计量分析 大数据 网络编程 WEB编程 通讯编程 游戏编程多媒体linux 外挂编程 程序API图像处理 嵌入式/单片机 数据库编程 控制台 进程与线程 网络安全 汇编语言 硬件编程 软件设计 工程标准规等。其中代写编程、代写程序、代写留学生程序作业语言或工具包括但不限于以下范围:C/C++/C#代写Java代写IT代写Python代写辅导编程作业Matlab代写Haskell代写Processing代写Linux环境搭建Rust代写Data Structure Assginment 数据结构代写MIPS代写Machine Learning 作业 代写Oracle/SQL/PostgreSQL/Pig 数据库代写/代做/辅导Web开发、网站开发、网站作业ASP.NET网站开发Finance Insurace Statistics统计、回归、迭代Prolog代写Computer Computational method代做因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp
网友评论