Assignment: Modeling a Numerical Calculator img {border-style: solid; border-width: 2px} window.onload = function() { /** * The parameter for the start() method defines the width of the * navigation pane. * If the parameter is omitted a default value of 12em is used. */ Start.start("14em"); }; This assignment highlights the importance of modeling and design in object-oriented programming. You are given code that implements a simple numerical calculator, which you will gradually enhance. The code benefits from modeling and design because: It is based on a state transition model that is easy to modify and extend, and It benefits from code reuse provided by class inheritance The Design How to Proceed Submission Provided Files UML Lab NetBeans Lab This section describes how the code you are given has been designed, and how you will modify both the design and its implementation. Make sure you understand the aspects of this design. You will want to return to this section when you are ready to proceed with the assignment. SimpleCalculator TokenDispenser The Evaluator NoPrecedenceCalculator PrecedenceCalculator ParenthesisCalculator Javadoc See the menu for provided class documentation. TokenDispenser SimpleCalculator In the NetBeans lab exercise (see menu to the left), you were given a Console class that presented a window in which input could be entered and results echoed to the display area (see right top). Console makes use of the JavaFX GUI framework, which you have yet to learn. At this point, however, that does not matter, because Console is designed to be extended by classes that do not have to do any GUI programming — they only have to provide code that handles input in a specific way. You are given a SimpleCalculator class that extends Console and allows simple arithmetic expressions to be evaluated (see right bottom). The inheritance relationship between SimpleCalculator and Console is shown in UML as: In order to evaluate arithmetic expressions, we need to read and return the various basic elements of the expressions, including numbers, operators, and the left and right parentheses. This process, called parsing, is supported at a rudimentary level by the StreamTokenizer class in the java.io package of the Java Standard Library. You are given a custom TokenDispenser class that extends the StreamTokenizer library class for the purposes of arithmetic expression evaluation: SimpleCalculator overrides the handleInput method of the Console class by handing the input to a stack-based shift/reduce expression evaluator, implemented by the evaluate method. The evaluate method is modeled by the state diagram you produced for the UML lab exercise (see diagram at right; see UML lab exercise in menu to the left). The evaluator for this state machine is simple: it can only evaluate expressions like "17.4" and "10/3". It cannot evaluate "2*3+4", for example. In Backus-Naur form (BNF), the evaluator can evaluate expressions of the form NUM [OP NUM] (NUM is a number, OP is an operator, and [...] means "zero or one occurrences of ..."). Use the menu at left to follow an example stack trace on 10/3. Empty Stack Process Operand 1 Process Operator Process Operand 2 Reduce Stack When the evaluation begins, the stack is empty: The first token, 10, is obtained and shifted onto the stack. The machine state is Number1: The second token, /, is obtained and shifted onto the stack. The machine state is Operator: The third token, 3, is obtained and shifted onto the stack. The machine state is Number2: Since there are no more tokens, the token dispenser indicates this with an EOF indication, the machine goes into state End, and the stack is reduced to the value of 10/3. The value of the expression is left as the only element on the stack: A simple change to the initial state diagram produces a model for a calculator that can evaluate 2*3+4 as 10. The same change will evaluate 2*3+4*5 as 50. Note that this new evaluator does not recognize operator precedence. If it did, 2*3+4*5 would evaluate as 26. In BNF, this evaluator can evaluate expressions of the form NUM [OP NUM]* ([...]* means "zero or more occurrences of ..."). You will create a class called NoPrecedenceCalculator that implements this new evaluation model. It can reuse code by extending SimpleCalculator but it must override the evaluate method: Operator precedence requires that the * and / operators have higher precedence than + and -. Enforcing operator precedence requires scanning an expression for consecutive operators, and if the second operator has higher precedence than the first, it must be applied before the first is applied. Thus, 2*3+4*5 evaluates as 26. Handling precedence in our evaluator does not require any change to the structure of the state machine; it only requires a change in the way the stack is reduced. You will create a class called PrecedenceCalculator that will inherit from NoPrecedenceCalculator but override the reduce method as shown below. Operator precedence introduces the possibility that the reducing process needs to iterate. See the menu at left for an example. After Shifting Reducing Reducing Again When evaluating 2+3*4, the stack will come to look like this: When the token dispenser indicates no more input, the state machine must reduce the stack: The stack must be reduced again to finish the input: Note that only one token, the EOF indicator, triggers these two reductions. Useful calculators allow parentheses to override the usual precedence rules. For example, 2*(3+4)*5 evaluates as 70. Handling parentheses in our state diagram requires new states corresponding to the left and right parentheses, and new transitions in and out of them. Thus the evaluate method must be overridden. Since encountering a right parenthesis triggers stack reductions the reduce action must also be changed. You will create a class called ParenthesisCalculator that will inherit from PrecedenceCalculator but override the evaluate and reduce methods: This section walks you through the process of turning the SimpleCalculator into one which handles precedence and parentheses. At each step, you will modify the simple calculator state diagram that you created for the UML lab exercise. These diagram modifications are an important part of the modeling and design process, and will be graded along with your code. You must save a copy of the diagram at each step and include it as part of your submission. Setup and Test Project Step 1: No Precedence Step 2: Precedence Step 3: Parentheses Download this Calculator.zip file and use the NetBeans Import Project feature to create the Calculator project. Your project should have this structure: Test It Test the SimpleCalculatorTest.java file. You should get a window like: Try various inputs to observe its behavior. Then close the window by clicking X on the window's title bar. The test cases coded in the SimpleCalculatorTest class will be run and you should get these results in the Test Results window: In the Output window, you should also see: -------------------------------------------------------
T E S T S
-------------------------------------------------------
Running calculator.SimpleCalculatorTest
testResults passed
testErrors passed
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0
In this step you will implement a calculator that can evaluate inputs of arbitrary length, without accounting for operator precedence. You will: Alter the original state diagram Create a new class that implements the new state transition model Test the new class with provided test cases This general procedure will be followed for the remaining steps as well. Stack Use State Diagram NoPrecedenceCalculator.java Since operator precedence is ignored, the stack is reduced when possible. Here is a trace of the stack when evaluating 2 + 3 * 4: Using Violet, open the State.violet file that you created and submitted for the UML lab exercise: Change the title note to read "State Diagram for a Shift-Reduce Calculator Without Precedence for Expressions of the form NUM [OP NUM]*" Change the diagram itself so that it conforms with the new title. Hints: To handle expressions of arbitrary length, a single Number state should replace the separate states Number1 and Number2. The diagram should loop back to Number as appropriate. The action of the Operator state must be modified. What must happen if an operator is encountered and NUM OP NUM is already on the stack? Use Violet's File → Export to → Image file option to save your diagram as no-precedence.png You need to complete the NoPrecedenceCalculator class, shown below. As described in the Design section, this class must be a subclass of SimpleCalculator to inherit its features. A class template is given for you in the project: This class needs to implement the evaluate method, overriding the one in SimpleCalculator. Look at how SimpleCalculator implements the original state diagram, then write your evaluate method to implement your modified diagram. Hints: Note that SimpleCalculator defines a public enumerated type called State one of whose values is NUMBER You will need to use the inherited getDispenser method so that you can advance the token dispenser as needed Like the original evaluate method, yours will need to loop until the input is exhausted, advancing to the next token, shifting tokens onto the stack, and reducing the stack as necessary Be sure that each time through the loop the inherited setState method is used to change the state of the evaluation Be sure that whenever a token is acquired for which your state diagram is not defined, a syntax error is signaled using the inherited syntaxError method. Take a look at the test file NoPrecedenceCalculatorTest.java (see Provided Files) for examples of erroneous input and the exact wording of error messages. Test It Test the NoPrecedenceCalculatorTest.java class, shown below. As with the simple calculator test, you will first be able to enter some expressions manually. After exiting the calculator, the coded tests will be run and if successful you will get the same results as with the simple calculator. Don't move to the next step until you've passed this one. In this step you will implement a calculator that can evaluate inputs of arbitrary length, accounting for operator precedence, but not allowing parentheses. Stack Use State Diagram PrecedenceCalculator.java Since operator precedence is respected, the stack is reduced according to precedence rules. Here is a trace of the stack when evaluating 2 + 3 * 4: Using Violet: Change the title note to read "State Diagram for a Shift-Reduce Calculator With Precedence and Without Parentheses for Expressions of the form NUM [OP NUM]*" Change the diagram itself so that it conforms with the new title. Hints: The states and state transitions themselves do not need to be changed The action taken when reducing the stack (as indicated in the diagram note) must be changed: If NUM OP NUM is on the stack and the end of the input is reached, what must happen? If NUM OP NUM is on the stack and the next token is an operator, what must happen? Note that the reducing process may have to repeat. For example, when the end of 2+3*4 is reached, the stack must reduce to 2+12 and then immediately to 14 Use Violet's File → Export to → Image file option to save your diagram as with-precedence.png As described in the Design section, this class must be a subclass of NoPrecedenceCalculator to inherit its features. A class template is given for you in the project: This class needs to implement the reduce method, overriding the one in SimpleCalculator. Write your reduce method to implement your modified diagram. Hints: Several methods inherited from SimpleCalculator, namely numOpNumOnStack and reduceNumOpNum, are useful You will need to use the inherited getDispenser method so that you can use TokenDispenser methods such as tokenIsEOF and tokenIsOperator In order to peek down the stack without popping, you can use the get method that the Stack class inherits from Vector (see the java.util package) To handle the possibility of multiple reductions for one input token, it is helpful to employ a while loop controlled by a boolean valued method that returns whether the stack is reducible Test It Test the PrecedenceCalculatorTest.java class, shown below. As with the simple calculator test, you will first be able to enter some expressions manually. After exiting the calculator, the coded tests will be run and if successful you will get the same results as with the previous tests. Don't move to the next step until you've passed this one. In the final step you will implement a calculator that handles both operator precedence and parentheses. Stack Use State Diagram ParenthesisCalculator.java The stack is used to both enforce operator precedence and respect parenthesis levels. Here is a trace of the stack when evaluating (2 * (3 + 5)): Using Violet: Change the title note to read "State Diagram for a Shift-Reduce Calculator With Precedence and Parentheses*" Change the diagram itself so that it conforms with the new title. Hints: There need to be new states corresponding to the left and right parentheses, with appropriate transitions into and out of them Make sure that transitions exist for every legal occurrence of left and right parentheses The action taken when reducing the stack (as indicated in the diagram note) must be changed: When a right parenthesis is encountered, the same (possibly multiple) reductions must be triggered as when EOF is encountered If ( NUM ) is on the stack, what must happen? If ( NUM OP NUM ) is on the stack, what must happen? If ( NUM OP NUM OP NUM) is on the stack, what must happen? When the end of input is reached, one of the actions must be to check for mismatched parentheses. Mismatched parentheses occur if the end of input has been reached and the stack does not contain a single number. Use Violet's File → Export to → Image file option to save your diagram as with-parens.png As described in the Design section, this class must be a subclass of PrecedenceCalculator to inherit its features. A class template is given for you in the project: This class needs to override both the evaluate and reduce methods to implement your modified diagram. Hints: Note that SimpleCalculator's public enumerated type State includes the values LEFT_PAREN and RIGHT_PAREN that can be used by evaluate Take a look at the test file ParenthesisCalculatorTest.java (see Provided Files) for examples of erroneous input and the exact wording of error messages. When the end of input has been reached and all reductions have been performed, if it is not the case that there is a single element (the expression value) on the stack, then there have been mismatched parentheses Test It Test the ParenthesisCalculatorTest.java class, shown below. As with the previous tests, you will first be able to enter some expressions manually. After exiting the calculator, the coded tests will be run and if successful you will get the same results as with the previous tests. The files required for this assignment are available from the menu on the left. TokenDispenser.java Precision.java SimpleCalculator.java SimpleCalculatorTest.java NoPrecedenceCalculator.java NoPrecedenceCalculatorTest.java PrecedenceCalculator.java PrecedenceCalculatorTest.java ParenthesisCalculator.java ParenthesisCalculatorTest.java When your calculator project is working correctly: Make sure your identifying information is in the class comments of all class files Use the NetBeans Export Project feature to create Calculator.zip in a location other than your Calculator project. Submit the following four files by going to and clicking Submission under Assignment: The Importance of Modeling and Design. no-precedence.png (state diagram for Step 1) with-precedence.png (state diagram for Step 2) with-parens.png (state diagram for Step 3) Calculator.zip (your exported project) Note the general Submission Policy in the menu at left. Your project will be inspected and run by the lab instructor. For full credit your project must pass the provided tests. Grading criteria: Successful completion of Step 1 including correct state diagram: 8 points Successful completion of Step 2 including correct state diagram: 8 points Successful completion of Step 3 including correct state diagram: 14 points Submission Policy
