CSE205 Object Oriented Programming and Data Structures Programming Project 4 ::

CSE205 Object Oriented Programming and Data Structures Programming Project 4 :: 25 pts1 Submission InstructionsCreate a folder named <asuriteid> where asuriteid is your ASURITE user id (for example, since my ASURITE user id iskburger2 my folder would be named kburger2) and copy all of your .java source code files to this folder. Do not copy the.class files or any other files. Next, compress the <asuriteid> folder creating a zip archive file named <asuriteid>.zip(mine would be named kburger2.zip). Upload <asuriteid>.zip to the Project 4 dropbox by the project deadline. Thedeadline is 11:59pm Wed 30 Apr. Consult the online syllabus for the late and academic integrity policies.2 Learning Objectives1. Complete all of the learning objects of the previous projects.2. To implement a GUI interface and respond to action events.3. To use the linked list, stack, and queue classes.3 BackgroundIn the lecture notes and video lectures for Stacks and Queues : Sections 3 – 7 we discussed an application that evaluatesan arithmetic expression written in infix notation such as:(-1 - -2) * -(3 / 5)Infix notation is the usual algebraic notation that we are all familiar with where a binary operator (a binary operator is anoperator that has two operands) is written between the left-hand and right-hand operands. For example, in the expressionabove, the left-hand operand of the subtraction operator is -1 and the right-hand operand is -2. Some operators, such asthe negation operator, are unary operators meaning there is only one operand. For negation, the operand is written to theright of the negation operator. Therefore, this expression contains six operators: negation, subtraction, negation,multiplication, negation, and division.In the algorithm that evaluates the expression, we also treat a left parenthesis as an operator, which it is not, but duringthe evaluation we have to push left parentheses onto the operator stack.In an infix arithmetic expression, each operator has a precedence level, which for a left parenthesis, is different when it ison the operator stack as opposed to when it is not (this will become clear when you read the trace of the algorithm for theabove expression; see page 3):Operator Normal Precedence Level Stack Precedence Level( 5 0– 4 4* / 3 3+ – 2 2) 1 1Right parentheses really don't have precedence because they are not pushed on the operator stack, but we assign them aprecedence level of 1 for consistency. The algorithm discussed in the notes did not handle the negation operator so I havemodified it to handle negation. Here is the revised algorithm:Method evaluate(In: pExpr as an infix expression) Returns DoubleCreate operatorStack -- Stores OperatorsCreate operandStack -- Stores OperandsWhile end of pExpr has not been reached DoScan next token in pExpr -- The type of token is TokenIf token is an operand ThenConvert token to Operand object named numberoperandStack.push(number)Arizona State University Page 1CSE205 Object Oriented Programming and Data Structures Programming Project 4 :: 25 ptsElseIf token is an InstanceOf LeftParen ThenConvert token to LeftParen object named parenoperatorStack.push(paren)ElseIf token is an InstanceOf RightParen ThenWhile not operatorStack.peek() is an InstanceOf LeftParen Do topEval()operatorStack.pop() -- Pops the LeftParenElseIf token is Negation, Addition, Subtraction, Multiplication, or Division ThenConvert token to Operator object named operatorWhile keepEvaluating() returns True Do topEval()operatorStack.push(op)End WhileWhile not operatorStack.isEmpty() Do topEval()Return operandStack.pop()End Method evaluateMethod keepEvaluating() Returns True or FalseIf operatorStack.isEmpty() Then Return FalseElse Return stackPrecedence(operatorStack.peek()) ≥ precedence(operator)End Method keepEvaluatingMethod topEval() Returns Nothingright ← operandStack.pop()operator ← operatorStack.pop()If operator is Negation Then operandStack.push(-right)Else left ← operandStack.pop()If operator is Addition Then operandStack.push(left + right)ElseIf operator is Subtraction Then operandStack.push(left - right)ElseIf operator is Multiplication Then operandStack.push(left * right)Else operandStack.push(left / right)End IfEnd Method topEvalMethod precedence(In: Operator pOperator) Returns IntIf pOperator is LeftParen Then Return 5ElseIf pOperator is Negation Then Return 4ElseIf pOperator is Multiplication or Division Then Return 3ElseIf pOperator is Addition or Subtraction Then Return 2Else Return 1End Method precedenceMethod stackPrecedence(In: Operator pOperator) Returns IntIf pOperator is LeftParen Then Return 0ElseIf pOperator is Negation Then Return 4ElseIf pOperator is Multiplication or Division Then Return 3ElseIf pOperator is Addition or Subtraction Then Return 2Else Return 1End Method stackPrecedenceArizona State University Page 2CSE205 Object Oriented Programming and Data Structures Programming Project 4 :: 25 ptsIt would be worthwhile to trace the algorithm using the above expression to make sure you understand how it works:1. Create the operand and operator stacks. Both are empty at the beginning.2. Scan the first token ( and push it onto the operator stack.3. Scan the next token – (negation) and push it onto the operator stack.4. Scan the next token 1 and push it onto the operand stack.5. Scan the next token – (subtraction). Since the operator on top of the operator stack (negation) has higher precedencethan subtraction, evaluate the top (note: negation is a unary operator so there is only one operand to be popped fromthe operand stack):a. Pop the top number from the operand stack. Call this right = 1.b. Pop the top operator from the operator stack. Call this operator = – (negation).c. Evaluate operator and push the result (-1) onto the operand stack.d. Now push the subtraction operator onto the operator stack.6. Scan the next token – (negation). Since the operator on top of the stack (subtraction) has precedence less thannegation, push the negation operator onto the operator stack.7. Scan the next token 2 and push it onto the operand stack.8. Scan the next token ). Pop and evaluate operators from the operator stack until the matching ( is reached.a. The top operator is a unary operator (negation):Pop the top number from the operand stack. Call this right = 2.Pop the top operator from the operator stack. Call this operator = – (negation).Evaluate operator and push the result (-2) onto the operand stack.b. The top operator is a binary operator (subtraction):Pop the top number from the operand stack. Call this right = -2.Pop the top number from the operand stack. Call this left = -1.Pop the top operator from the operator stack. Call this operator = – (subtraction).Evaluate operator and push the result (1) onto the operand stack.c. The top operator is ( so pop it.9. Scan the next token * (multiplication). The operator stack is empty so push *.10. Scan the next token – (negation). Since negation has higher precedence than the operator on top of the operatorstack (multiplication) push the negation operator onto the operator stack.11. Scan the next token ( and push it onto the operator stack.12. Scan the next token 3 and push it onto the operand stack.13. Scan the next token / (division). Since the operator on top of the stack (left parenthesis) has higher precedence thandivision push / onto the operator stack. Now do you see why the precedence of ( changes when it is on the operatorstack?14. Scan the next token 5 and push it onto the operand stack.15. Scan the next token ). Pop and evaluate operators from the operator stack until the matching ( is reached.a. The top operator is binary operator (division):Pop the top number from the operand stack. Call this right = 5.Pop the top number from the operand stack. Call this left = 3.Pop the top operator from the operator stack. Call this operator = /.Evaluate operator and push the result (0.6) onto the operand stack.b. The top operator is ( so pop it.16. The end of the infix expression string has been reached. Pop and evaluate operators from the operator stack until theoperator stack is empty.a. The top operator is a unary operator (negation):Pop the top number from the operand stack. Call this right = 0.6.Pop the top operator from the operator stack. Call this operator = – (negation).Evaluate operator and push the result (-0.6) onto the operand stack.Arizona State University Page 3CSE205 Object Oriented Programming and Data Structures Programming Project 4 :: 25 ptsb. The top operator is a binary operator (multiplication):Pop the top number from the operand stack. Call this right = -0.6.Pop the top number from the operand stack. Call this left = 1.Pop the top operator from the operator stack. Call this operator = *.Evaluate operator and push the result (-0.6) onto the operand stack.17. The operator stack is empty. Pop the result from the operand stack (-0.6) and return it.4 Software RequirementsThe project shall implement a GUI calculator which accepts as input a syntactically correct arithmetic expression writtenin infix notation and displays the result of evaluating the expression. The program shall meet these requirements.1. The program shall implement a GUI which permits the user to interact with the calculator. Watch the Project 4video lecture for a demonstration of how the application works.2. When the Clear button is clicked, the input text field and the result label shall be configured to display nothing.3. When a syntactically correct infix arithmetic expression is entered in the input text field and the Evaluate button isclicked, the program shall evaluate the expression and display the result in the label of the GUI.4. When the Exit button is clicked, the application shall terminate.5. Note: you do not have to be concerned with syntactically incorrect infix expressions. We will not test your programwith such expressions.5 Software DesignRefer to the UML class diagram in Section 5.21. Your program shall implement this design.5.1 Main ClassThe Main class shall contain the main() method which shall instantiate an object of the Main class and call run() on thatobject. Main is completed for you.5.2 AddOperatorImplements the addition operator which is a binary operator. AddOperator is completed for you.5.3 BinaryOperatorThe abstract superclass of all binary operators. BinaryOperator is completed for you.5.4 DivOperatorImplements the division operator which is a binary operator. Complete the code in this file by using the AddOperator codeas an example.5.5 DList<E>Implements a generic doubly linked list where the type of each element is E. This file contains the same DList class thatwas provided in the Week 6 Source zip archive, except I have changed it to be a generic class so we can use it to store anyclass of objects. DList is completed for you.5.6 ExpressionRepresents an infix expression to be evaluated. Use the provided pseudocode as a guide in completing this class.5.7 LeftParenRepresents a left parenthesis in the expression. LeftParen is completed for you.5.8 MultOperatorImplements the multiplication operator which is a binary operator. Complete the code in this file by using the AddOperator code as an example.Arizona State University Page 4CSE205 Object Oriented Programming and Data Structures Programming Project 4 :: 25 pts5.9 NegOperatorImplements the negation operator which is a unary operator. Complete the code in this file by using the AddOperatorcode as an example. Note, however, that negation is a unary operator.5.10 OperandAn operand is a numeric value represented as a Double. Implement the class using the UML class diagram as a guide.5.11 OperatorOperator is the superclass of all binary and unary operators. Implement the class using the UML class diagram as a guide.Note that all of the non-constructor methods are abstract, i.e., none of them are implemented in Operator.5.12 ParenthesisParenthesis is the superclass of LeftParen and RightParen. These are treated as a weird sort of Operator because we needto be able to push LeftParens on the operator stack when evaluating the expression. Parenthesis is completed for you.5.13 Queue<E>Implements a generic queue data structure using a DList<E> list to store the elements. This is the same class that wasprovided in the Week 6 Source zip archive except I have modified it to be a generic class. Queue is completed for you.5.14 RightParenRepresents a right parenthesis in the expression. RightParen is completed for you.5.15 Stack<E>Implements a generic stack data structure using a DList<E> list to store the elements. This is the same class that wasprovided in the Week 6 Source zip archive except I have modified it to be a generic class. Stack is completed for you.5.16 SubOperatorImplements the subtraction operator which is a binary operator. Complete the code in this file by using the AddOperatorcode as an example.5.17 TokenToken is the abstract superclass of the different types of tokens that can appear in an infix expression. Token is completedfor you.5.18 TokenizerThe Tokenizer class scans a string containing an infix expression and breaks it into tokens. For this project, a token willbe either an Operand (a double value), a LeftParen or RightParen, or an arithmetic UnaryOperator (NegOperator) orBinaryOperator (one of AddOperator, SubOperator, MultOperator, or DivOperator). Tokenizer is completed for you.5.19 UnaryOperatorUnaryOperator is the superclass of all unary operators. UnaryOperator is completed for you.5.20 ViewThe View implements the GUI. Read the comments and implement the pseudocode.Arizona State University Page 5CSE205 Object Oriented Programming and Data Structures Programming Project 4 :: 25 pts5.21 UML Class DiagramThe UML class diagram is provided in the zip archive in UMLet format and as a PNG image. Your program shallimplement this design.Arizona State University Page 6CSE205 Object Oriented Programming and Data Structures Programming Project 4 :: 25 pts5.21 UML Class Diagram (continued)Arizona State University Page 7CSE205 Object Oriented Programming and Data Structures Programming Project 4 :: 25 pts6 Additional Project Requirements1. Format your code neatly. Use proper indentation and spacing. Study the examples in the book and the examples theinstructor presents in the lectures and posts on the course website.2. Put a comment header block at the top of each method formatted thusly:/*** A brief description of what the method does.*/3. Put a comment header block at the top of each source code file formatted thusly://********************************************************************************************************// CLASS: classname (classname.java)//// COURSE AND PROJECT INFO// CSE205 Object Oriented Programming and Data Structures, semester and year// Project Number: project-number//// AUTHOR// your-name (your-email-addr)//********************************************************************************************************Arizona State University Page 8