CSCI162 - Lab 10 1 Lab 10: Prefix Evaluator 1 Objective In this assignment you will read and figure out how to use several classes that I provide, write your own class from scratch, and implement a classic use of recursion. 2 Background: Prefix Expressions In last week’s lab we evaluated postfix expressions, where the operator comes after the operands. The same person who invented them also invented prefix expressions, where the operator comes before the operands. Here is an example: + - 5 3 * 8 2 Like with postfix expressions, no parenthesis are needed. This means that we should first subtract 3 from 5, then multiply 8 by 2, then add those two results, like this: + - 5 3 * 8 2 + 2 * 8 2 + 2 16 18 You wouldn’t be able to solve this using the algorithm that we wrote for postfix expressions. Surprisingly, there is a different stack-based algorithm that will work. But we are going to solve the problem in a different way, by using recursion. (There is actually a hidden stack in all recursive programs: the call stack, in which the computer remembers all of the method calls that are waiting to finish.) 3 Setup Create a new Java Project (Lab10). Download the Lab10Files.zip file, unzip it, and place the files it contains into your project’s source folder. You should have the following files: Token A class that represents a component of an arithmetic expression (same as Lab 09) TokenScanner A class that breaks apart a mathematical expression into individual tokens (same as Lab 09). P02TestFunctionality My tests for the class that you will write. PrefixProgram A very simple program you can run to manually test your code. CSCI162 - Lab 10 2 4 Class Specifications You must create your own class, which must be named PrefixEvaluator. This class has two required methods: 1 /** 2 * E v a l u a t e s a p r e f i x m a t h em a t i c al e x p r e s s i o n . 3 * 4 * @param i n p u t A S t r i n g c o n t a i n i n g t h e e x p r e s s i o n . 5 * @re turn A S t r i n g c o n t a i n i n g t h e v a l u e o f t h e e x p r e s s i o n , or an e r r o r message i f t h e r e was a p r oblem . 6 */ 7 public static String evaluate ( String input ) 8 9 /** 10 * E v a l u a t e s t h e n e x t sub−e x p r e s s i o n f oun d i n a sc a n ne r . 11 * 12 * @param sc a n ne r A TokenScanner c o n t a i n i n g a t l e a s t one p r e f i x ( s ub )−e x p r e s s i o n . 13 * @re turn The r e s u l t o f t h e f i r s t sub−e x p r e s s i o n f o un d i n t h e sc a n ne r . 14 */ 15 private static Double evaluateSub ( TokenScanner scanner ) The private method is the one that does all of the work, recursively. If the private method finds an error in the input, it should throw an appropriate exception. All the public method does is call the private one and handle errors. Just like the previous lab, it must catch any exceptions that get thrown and instead return exactly the following error messages: input string is empty or all spaces or tabs "No input." NoSuchElementException thrown by TokenScanner "Not enough operands." evaluation ended before end of input "Computed answer, but not all input used." parentheses in input "( has no meaning here." / ") has no meaning here." In the PostfixExpression class it was possible to avoid exceptions entirely. In the PrefixExpression class this is not possible, because the private method must return a Double if it returns at all. So if the private method encounters an exceptional situation it should throw something (probably an IllegalArgumentException) and the public method should catch it. 5 Algorithm And Example What is the simplest possible prefix expression? It’s the same as the simplest possible postfix or infix expression: a single number! So that should be our base case. The value of such an expression is the number itself. An operator leads to the recursive case. We know that the two operands come after the operator, so when we find an operator we should recursively evaluate the first sub-expression after it, then recursively evaluate the second sub-expression after it, then apply the operator to those two results to get our answer. Consider our original example: + - 5 3 * 8 2. CSCI162 - Lab 10 3 Alice first finds an operator (’+’), so she asks Bob to solve the first sub-expression after it, and waits for his answer. – Bob also finds an operator (’-’), so he asks Cindy to solve the first sub-expression after it, and waits for her answer. * Cindy finds a number (5), and so she answers 5 back to Bob. – Bob thanks Cindy for her answer, and remembers it. Then he asks Dan to solve the next sub-expression, and waits for her answer. * Dan finds a number (3), and so he answers 3 back to Bob. – Bob thanks Dan for his answer, and remembers it. Then he applies his operator (’-’) to the answers he got from Cindy (5) and Dan (3). Then he answers 2 back to Alice. Alice thanks Bob for his answer, and remember it. Then she asks Ellen to solve the next sub-expression, and waits for her answer. – Ellen finds an operator (’*’), so she asks Fred to solve the first sub-expression after it, and waits for his answer. * Fred finds a number (8), so he answers 8 back to Ellen. – Ellen thanks Fred for his answer and remembers it. Then she asks Gail to solve the next sub-expression, and waits for her answer. * Gail finds a number (2), so she answers 2 back to Ellen. – Ellen thanks Gail for her answer, and remembers it. Then she applies her operator (’*’) to the answers she got from Fred (8) and Gail (2). So she answers 16 back to Alice. Alice thanks Ellen for her answer, and remembers it. Then she applies her operator (’+’) to the answers she got from Bob (2) and Ellen (16), and concludes that 18 is the value of the entire expression. 6 Grading AutoLab Problem Points Autograded Description 01 structure 2 yes Does the program have the right components? 02 functionality 88 yes Do the methods work? 03 style 10 partial Is the program written with good style? Note that a non-recursive solution will earn no points, even if it solves the problem. 7 Submitting Your Work Make sure that you have submitted your final version of your file to AutoLab, and that you have 100/100 autograded points. You do not need to submit your work through D2L – I will look at whatever your last AutoLab submission is.