Postfix and Infix Evaluators Solution

Overview




For this project, you will first implement a generic, linked-list based Stack class. Then you will use the Stack class to implement an evaluator for postfix expressions (of integers), and also an evaluator for infix expressions (of integers).




Learning Goals




Write a generic, unbounded Stack class implemented using linked list.




Use the Stack class you wrote to implement a postfix evaluator, in order to evaluate postix expressions such as 3 4 + 6 5 - *.




Use the Stack class you wrote to implement an infix evaluator, in order to evaluate infix expressions such as (3 + 4)* (6 - 5).




Learn to use Exceptions to handle errorneous situations in complex programs. Continue practicing using JUnit tests to test and debug non-trivial code.




General Information [Common]




Reminder: Copying partial or whole solutions, obtained from other students or elsewhere, is academic dishonesty. Do not share your code with your classmates, and do not use your classmates’ code. If you are confused about what constitutes academic dishonesty you should re-read the course policies. We assume you have read the course policies in detail and by submitting this project you have provided your virtual signature in agreement with these policies.




For some projects, it may be useful for you to write additional java files. Any java file you write MUST be placed in the provided src directory of your Eclipse project.




When submitting your project, be sure to remove all compilation errors. Any compilation errors will cause the autograder to fail to run, and consequently you will receive a zero for your submission. No Exceptions!




In the test directory, we provide several JUnit tests that we refer to as the public tests. We recommend you run the tests often and use them as starting points to test your project. In addition, some of the java files come with their own main functions. You can run them as Java applications to interact with the project.




Be aware that the autograder will use a more comprehensive set of tests (referred to as private tests) to grade your project. These tests are hidden from you. We recommend that you think about possible test cases and add new @Test cases to your public test files as part of your programming discipline. In particular, you should consider:




Do your methods handle edge cases such as integer arguments that may be positive, negative, or zero. Many methods only accept arguments that are in a particular range.




Does your code handle cases such as when an array or list is empty, or has reached full capacity?




More complex tests will be project-specific. To build good test cases, think about ways to exercise methods. Work out the correct result for a call of a method with a given set of parameters by hand, then add it as a test case.




Import Project into Eclipse [Common]




Begin by downloading the starter project and importing it into your workspace. It is very important that you do not rename this project as its name is used during the autograding process. If the project is renamed, your assignment will not be graded, and you will receive a zero.




The imported project may have some compilation errors, but these should not prevent you from getting started. Specif-ically, we may provide JUnit tests for classes that do not yet exist in your code. You can still run the other JUnit tests. After completing your code, the compilation errors should be gone.







The project should normally contain the following root items:



src This is the source folder where all code you are submitting must go. You can change anything you want in this folder (unless otherwise specified), you can add new files, etc.




support This folder contains support code that we encourage you to use (and must be used to pass certain tests). You must not change or add anything in this folder. To help ensure that, we suggest that you set the support folder to be read-only. You can do this by right-clicking on it in the package explorer, choosing Properties from the menu, choosing Resource from the list on the left of the pop-up Properties window, unchecking the Permissions check-box for Owner-Write, and clicking the OK button. A dialog box will show with the title “Confirm recursive changes”, and you should click on the “Yes” button.




test The test folder where all of the public unit tests are available. You can feel free to add your own tests here.




JUnit 4 A library that is used to run the test programs.




JRE System Library This is what allows Java to run; it is the location of the Java System Libraries.




If you are missing any of the above or if errors are present in the project (other than as specifically described below), seek help immediately so you can get started on the project right away.




Project Details




Requirement: you may NOT use any Java class from the java.util package (e.g. Stack, ArrayList, Vector etc.).




Doing so will result in a grade of 0.




Files to Complete. In the src folder, you can find each of the files listed below, which you need to complete. Each of them has JUnit tests associated with them. For full credit, you must correctly implement each class according to the specifications given in this description (including Exceptions you are expected to throw to indicate various errors in the expressions, with specific messages carried by these Exceptions). Places that need your work are clearly marked by TODO in the source code.




stack.LinkedStack.java A stack data structure that uses a generic LLNode<T structure to allow for un-bounded stack size. Remember, you may NOT use any Java class from the java.util package.




evaluator.PostfixEvaluator.java A postfix expression evaluator. Specifically, you need to implement




the evaluate_step method.




evaluator.InfixEvaluator.java An infix expression evaluator. Specifically, you need to implement the evaluate_step method, and complete the evaluate method where it’s marked TODO.




1. Implementing LinkedStack




You need to implement a stack data structure using a linked list to allow for unbounded capacity. Carefully read the comments in stack.LinkedStack.java to understand how to complete each method. A few quick notes below:




You should use the LLNode<T data structure as linked list node. Note that both class variables in LLNode< T are public so you can access them directly without setters and getters.




You don’t have to create a constructor for LinkedStack – if you don’t define a constructor, Java provides a default constructor that automatically initializes variables to 0 for integers, and null for references.



Please note that the LinkedStack class does NOT throw any exception – this is different from the code presented in lecture slides. Instead, the pop() and top() methods return null when stack is empty. So the caller methods can check the return value and compare with null to see if the stack is empty (of course you




can also explicitly call isEmpty() to check). Sometimes it’s more convenient to use return values to indicate error situations rather than throwing exceptions (which need to be wrapped within try-catch clause).




For the size() method, create a class variable int size; to keep track of the number of elements. This is way more efficient than traversing the list each time. Once you complete the LinkedStack class, run PublicLinkedStackTest in the test folder and make sure you pass all the tests provided.




Postfix Expressions and Evaluator



As discussed in lecture, a postfix expression, also known as Reverse Polish Notation (RPN), is a notation where the operator appears after the operands. This is different from our familiar mathematical expressions (called infix notation) where the operator appears between two operands. For example, the postfix expression 4 5 7 2 + is equivalent to the infix expression 4 (5 (7 + 2)). Postfix expression is particularly easy to evaluate using a computer program, and it does not need parentheses as the order of operations is intrinsic in the notation.




Operands and Operators. For simplicity, the operands (i.e. numbers) in the expressions are all Integers. This means the division operation performs Integer division. We assume there are five valid operators, namely addition +, subtraction , multiplication , division =, and negation !. The first four are binary operators, meaning each applies on two operands; the last one is a unary operator – it applies on only one operand and it negates the value of the operand (e.g. 5 ! = 5). Other than these five operators, all other operators (such as modulo %) are invalid / unsupported (after this project you can feel free to extend the program to handle other operators as you wish).




Expression Parser. The starter code has provided a simple parser (support.parser.ArithParser) that can split an input expression into an array of string tokens, each of which is either an operand or operator. For example, if the input is "10 20 ! +", the parser will break it down into an array of 4 strings f"10", "20", "!", "+"g which are called tokens. The postfix evaluator processes one token at a time, until all tokens have been processed. For an operand token, you can use Integer.parseInt(token) to convert it to its Integer value; for an operator token, use the String class’s .equals method to compare and find out what operator it is.




Note that symbol can either mean the subtraction operator, or indicate a negative sign. To avoid ambiguity, it should be followed by a space if it’s meant to be subtraction; and it should be followed immediately by a number if it is to indicate a negative sign. For example, in "10 5 - 6 /", is subtraction; and in "10 5 -6 /", 6 is a number.




Implement Postfix Evaluator. Go to evaluator.PostfixEvaluator.java and you will see TODO com-ments. Before starting, thoroughly review the lecture slides to make sure you understand how to use a stack to evaluate postfix expressions. The loop over all tokens is in the evaluate method, which you do NOT need to modify at all. Your changes should be completely inside the evaluate_step method, which processes one token at a time. The stack you will need is already created for you at the beginning of the class.




Exceptions. A postfix expression may contain various errors, and your program should detect such situations and throw an Exception object with a message. Below are the specific errors that need to be detected and the exact message to be carried in each case. You can use throw new Exception("message"); to raise an exception, and the JUnit test looks at the exception message to check whether you have detected each error situation correctly.




If any stack.pop() statement returns a null value, it indicates a shortage on operands. You should throw an exception with the exact message "too few operands". Note that a binary operator (+-*/) pops two elements from the stack, and a unary operator (!) pops one element from the stack.




If the denominator in a division operation is 0, throw an exception with message "division by zero".




If any operator other than +-*/! is encountered, throw an exception with message "invalid operator".




Once you complete the PostfixEvaluator class, run PublicPostfixEvaluatorTest to check whether your implementation passes all tests we prepared for you. You can also write additional tests, or run PostfixEvaluator class itself (it contains a main) method to write custom test cases that help you debug.




3. Infix Expressions and Evaluator




Although postfix expressions are easy for computers to evaluate, what we use on a day to day basis are infix expres-sions, where an operator appears in between two operands. In this section, you will learn to write an infix evaluator to compute the results of infix expressions.




Operands, Operators, and Parser. For the most part, the operands, operators, and parser are the same as in the postfix case. Specifically, operands are all Integers as before, and the parser is the same as before. The primary difference is that we now need to consider the precedence or priority of operators, since the precedence determines the order of operations. For example, in expression 3 + 4 5, the multiplication has higher precedence than addition, so 4 5 is calculated first, and the result gets added to 3 next.




We can use parentheses to change the order of operations. For example, if we want 3 + 4 to be performed first, we can do (3 + 4) 5. This is where infix expression gets more complicated than postfix: it’s a notation that we are more familiar with, but writing a program to evaluate it is more involved that postfix, because now you have to consider each operator’s precedence, and you have to consider the addition of parentheses.




Implement Infix Evaluator. Below we describe an algorithm for evaluating infix expression. We won’t have space here to prove its correctness but will leave it as an exercise for you after the project. Lafore’s Java textbook discusses how to convert an infix expression to postfix, which is worth reading and contains the basic idea of the proof. For now, you just need to follow the description below to implement the algorithm.




To begin, we need two stacks: an operators stack, and an operands stack. These are created for you at the beginning of the InfixEvaluator class. The algorithm below describes how to implement the evaluate_step method. It refers to a process_operator method which is explained shortly.




When the token is an operand, push it to the operands stack.



When the token is a left parenthesis (, push it to the operators stack.



When the token is a operator, and if either the operators stack is empty or the token’s precedence is greater than the operators stack’s top element, push the token to the operators stack.



When the token is a right parenthesis ), do process_operator (explained below) until a left parenthesis ( is encountered. Make sure the encountered ( is popped out from the operators stack.



Otherwise (i.e. when none of the above applies), do process_operator repeatedly until the current token’s precedence is greater than the operators stack’s top element (or if there is nothing left in the operators stack). Then push the current token to the operators stack.



After all tokens have been processed, do process_operator repeatedly until the operators stack is empty. If the expression is valid, the operands stack should have exactly one number left, which is the final result.



The process_operator method, which you need to write yourself, is quite similar to what you did for postfix expression. Specifically, it pops one operator from the operators stack, then depending on whether this is a unary operator (!) or binary operator (+ =), it pops one or two operands from the operands stack, applies the operator on the operand(s), and pushes the result back to the operands stack. That’s it.




To get an operator token’s precedence, you can call precedence(token). This method is already provided by the Evaluator class, which is InfixEvaluator’s parent class. As you can see in that method, it defines that the negate operator ! has a greater precedence than and =, which in turn have greater precedence than + and .




Making Sense of the Algorithm. Before starting to code, you should try a few infix expressions with the above algorithm to make sense of it, and gain some intuitions. For example, try 3 4 + 5: after token 4 is seen, the operands stack should have two numbers: 3 and 4, and the operators stack should have one operator . Next, you encounter




operator +, and since + has a lower precedence than , which is operators stack’s top element, condition (e) applies here, so you do process_operator to calculate 3 4, push the result 12 to the operands stack, and then push the operator + to the operators stack. This makes sense because has a greater precedence than +, so you can safely conclude that part of the expression before you move on. Finally, after all tokens have been processed (step (f)), the operands stack has two numbers: 12 and 5, and the operators stack has one element +. You do process_operator to calculate 12 + 5 = 17, and that’s the final number left in the operands stack.




Next try 3 + 4 5: this time, upon seeing operator , the operands stack has 3 and 4, and the operators stack has +. Because has greater precedence, you cannot proceed to calculate 3 + 4 first. Instead, condition (c) applies here, so you push operator to the operators stack. Eventually, in step (f), 4 5 will be calculated first, and 3 is added to the result of that. The intuition is that whenever you see an operator with greater precedence, you have to hold on to that part of the calculation until you encounter an operator that has equal or lower precedence.




Finally, try 3 (4 + 5 6). Technically, ( is not an operator. But since it’s stored in the operators stack, one clever trick we use here is that the precedence method assigns a precedence value to ( that’s lower than any real operators. This way, upon seeing token +, condition (c) is true, so + gets pushed to the operators stack. The stuff inside the parentheses will get evaluated after seeing token ), in which case condition (d) applies, and you do process_operator repeatedly until ( is encountered in the operators stack.




We encourage you to try a few more complex examples to convince yourself about the algorithm. Then proceed to implement the algorithm.




Exceptions. Below are the specific errors that need to be detected and the exact message to be carried in each case.




In process_operator method, if any operator other than +-*/! is encountered, throw an exception with message "invalid operator". If any pop from the operands stack returns a null value, throw an ex-ception with message "too few operands". If the denominator in a division operation is 0, throw an exception with message "division by zero".




In condition (d), if the operators stack becomes empty and you still haven’t found a left parenthesis, throw an exception with message "missing (".




Once you complete the InfixEvaluator class, run PublicInfixEvaluatorTest to check whether your implementation passes all tests we prepared for you. You can also write additional tests, or run InfixEvaluator class itself (it contains a main) method to write custom test cases that help you debug.




Validity of Infix Expression. We should point out that the algorithm described here is not meant to fully check the validity of an infix expression. You may be surprised to find that an expression like 2 3 + can successfully pass the evaluator without raising any exception. Additional checks can be added, such as by forbidding a number followed immediately by another number, but these are beyond the scope of this project, so we will ignore them for now.




Export and Submit [Common]




When you have completed this project, you should export an archive file containing the entire Java project. To do this, click on the postandinfix-student project in the package explorer. Then choose “File ! Export” from the menu. In the window that appears, under “General” choose “Archive File”. Then choose “Next” and enter a destination for the output file. Be sure that the project is named postandinfix-student (otherwise you may be exporting the wrong project!). Save the exported file with the zip extension.







Once you have the zip file ready, you can submit it to the online autograder (Gradescope). Please see the course website and/or documentation explaining how to use the online autograder. If you have any questions please be prompt in asking the course staff before it is too late to submit your solution. If you encounter any errors that look like the autograder failed and not your project, please let the instructors know.










Page 7 of 7