Attached in the PDF are the instructions for the assignment.In the Zip File are the Java files for the Assignment.
Page 1 of 3 Infix to Postfix Expression Assignment Assignment objective: Implement a dynamic array stack data structure and use it to implement the infix arithmetic expression to post fix arithmetic expression conversion algorithm. Overview: The arithmetic expressions given as input to your program contain operands which are positive integers or single letter variables. The arithmetic expressions given as input to your program can contain any of the operators: +, – , *, / as well as parenthesis. The operators have the usual precedence as given in the table below. Parenthesis have the highest precedence. The operators * and / have the next lowest precedence. The operators + and – have the lowest precedence. Precedence Operator Type Associativity 1 ( ) Parenthesis Left to Right 2 * / Multiplication Division Left to Right 3 + – Addition Subtraction Left to Right Here are some examples of expressions written in infix notation and their postfix notation equivalent: A simple infix expression: a+5 Written as a postfix expression: a 5 + A more complex infix expression: a + 156 * b Written as a postfix expression: a 156 b * + Another infix expression: a * 5 + b Written as a postfix expression: a 5 * b + Another infix expression: a + b * c – d Written as a postfix expression: a b c * + d – Another infix expression: a – (b + c) * d Written as a postfix expression: a b c + d * – Page 2 of 3 Infix to Postfix Algorithm: You’ll use a stack to process the operators and parenthesis in the arithmetic expression. Treat the arithmetic expression as a linear sequence of tokens. A token is a String that is an operand (positive integer or variable), an operator, or a left or right parenthesis. The data member ops is a stack of Strings, the data member postfix is a queue of Strings, and the parameter lineTokens is a queue of Strings. While lineTokens is not empty: 1. Dequeue a token from lineTokens and get its first character. 2. If the first character is a letter or digit, then the token is an Operand token. Enqueue the token onto the queue postfix. 3. If the first character is a left parenthesis, then the token is a Left Parenthesis token. Push the token onto the top of the stack ops. 4. If the first character is a right parenthesis, then the token is a Right Parenthesis token. a. Pop the operator at the top of the stack ops and enqueue the popped operator onto the queue postfix. b. Repeat step a above until the top of the stack ops contains a left parenthesis. c. Pop the left parenthesis at the top of the stack ops and discard it. 5. If the first character is one of the 4 operators: +, –, *, or /, then the token is an Operator token. a. If the stack ops is not empty and the operator at the top of the stack ops has a higher or equal precedence than the operator token just read, then pop the operator at the top of the stack ops and enqueue the popped operator onto the queue postfix. b. Repeat step a above until the stack ops is empty or the operator at the top of the stack ops has a lower precedence than the operator token just read. c. Finally, push the operator token just read onto the top of the stack ops. Note: Use the given method hasHigherOrEqualPrecedence to compare the precedence of two operators to see if the first operator has a higher precedence than the second operator. After the last token in the arithmetic expression is dequeued from the queue lineTokens and processed, pop any remaining operators from the top of the stack ops and enqueue the popped operator onto the queue postfix until the stack ops is empty. Design: 1. Download the files Assignment2.java, DynamicArrayStack.java, InfixToPostfix.java, InputReader.java, LinkedQueue.java, Queue.java, Stack.java, and TokenizeLine.java provided along with this assignment in Blackboard and include them in your project. 2. You cannot modify any of the code in the files InputReader.java, LinkedQueue.java, Queue.java, and TokenizeLine.java. Page 3 of 3 3. The file Stack.java contains the stack interface. You cannot modify any of the code in this file. 4. The file DynamicArrayStack.java implements a stack using an array as storage where the stack’s array grows and shrinks in size as discussed in class. You cannot change any of the code that is already in this file. You will write the code for the size, resize, push, top, and pop methods. 5. The file InfixToPostfix.java implements the infix to postfix conversion algorithm. You cannot change any of the code that is already in this file. You will write the code for the convertInfixToPostfix method to implement the infix to postfix algorithm as described on the previous page. You can add any additional methods to this class as needed but you must declare them private. You cannot and do not need to add any additional data members to this class. 6. The file Assignment2.java is the driver code for the assignment. You cannot and do not need to modify any of the code in this file. The main function receives, via the command line argument, the name of a text file containing lines of text. The main method creates an InputReader object and then calls the readAndReturnFileLines method of the InputReader object. The readAndReturnFileLines method returns a LinkedQueue of Strings containing the lines of text from the text file. The main method then dequeues each line of text from the LinkedQueue and passes the line of text to the generateTokenQueueFromLine method of the TokenizeLine class to create a LinkedQueue of Strings with each String in this queue being: a variable, a positive integer, an operator, or a left or right parenthesis. The main method finally passes this LinkedQueue to the convertInfixToPostfix method of the InfixToPostfix class which will convert the infix expression to its equivalent postfix expression returning the postfix expression back to the main method as a String to print. 7. Each line in the test file is an arithmetic expression written in infix notation. 8. The command to launch your program, assuming test.txt is the name of the text file, is: java Assignment2 test.txt 9. Do NOT use packages in your program. If you see the keyword package on the top line of any of your .java files then you created a package. 10. Do NOT use any graphical user interface code in your program! 11. Do NOT type any comments in your program. If you do a good job of programming it will be easy for me to determine the task of your code.