In this assignment, you’ll be implementing the “infix-to-postfix” and “postfix evaluation” algorithms simultaneously. You will then improve upon this by implementing error detection to give error messages about inputs, rather than just crashing.

Starting point

I hope project 1 taught you to never write an entire program before testing it. Right? Right?????? 😁

• ArrayStack.java, a stack implementation using an array.
• StackInterface.java, the interface ArrayStack implements.
• ExpressionError.java, an exception type.
• InfixExpressionEvaluator.java. This is the file you will modify.

Do not modify anything other than InfixExpressionEvaluator.java. We will be testing it with unmodified versions of the other files.

InfixExpressionEvaluator contains a good bit of code already. You do not need to change any of the methods we wrote. Instead, you will be filling in the methods which implement the “meat” of the algorithm. Basically, search for TODO: and do those things.

There is a main in InfixExpressionEvaluator so you can run it like java InfixExpressionEvaluator. It does nothing when you first download it, but it does run.

Implementing the TODO methods [70 points]

Check out sections 5.16 and 5.18 in the book (4th ed.). Those outline what you are doing. We already did the switch-case for you; the methods you implement are the code inside those cases.

You’re going to “squish” those two algorithms into one. Rather than having an “output”, you will push the operands as you encounter them and evaluate the operators as you pop them. We’ve already given you two stacks to hold these things.

Here are the methods you must fill in. They are all called by evaluate() as it finds tokens in the input.

• handleOperand(double) - called when a number is encountered.
• For example, 3, 900, 6.28 etc.
• handleName(String) - called when a name is encountered.
• A name is a special kind of operand.
• You must handle pi and e.
• You can use the Java Math.PI and Math.E constants.
• Don’t duplicate effort! You already have a method to handle an operand.
• For any other name, throw an ExpressionError with a descriptive message.
• handleOperator(char) - called when an operator is encountered.
• You must handle the following operands:

Symbol Operation Precedence Associativity
+ Addition Lowest Left
- Subtraction Lowest Left
* Multiplication Middle Left
/ Division Middle Left
^ Exponentiation Highest Right

Java has no exponentiation operator. You can type a ^ b in Java but it means something VERY different! Look it up. Use the Math.pow() method instead.

• The ^ operator is handled a little differently from the rest. The code in section 5.16 shows this.

• Basically, right-associative operators are super easy to deal with.
• handleOpenBracket(char) - called when an open bracket is encountered.
• You must allow (, {, and [.
• handleCloseBracket(char) - called when a close bracket is encountered.
• You must allow ), }, and ].
• handleRemainingOperators() - called at the end of parsing.
• After all tokens have been parsed, this is called to allow you to evaluate any operators still on the stack.

And last, you must fill in the return value of evaluate(). Right now it returns null. That’s bad. You want it to return the result of the expression evaluation.

Example inputs/outputs

Here are examples.

Suggestions

• Try just printing the arguments in each method at first.
• That will give you an idea of what methods are called, and in what order.
• Then work on doing the infix-to-postfix algorithm.
• You don’t have to do it “right” at first. Maybe just start by printing the output instead of evaluating.
• Check it against examples that you know the output for.
• Abstract your precedence-checking into a function like boolean isLowerPrecedence(char a, char b).
• That way, you can print out isLowerPrecedence('+', '*') and make sure it’s true, etc.
• Then work on evaluation.
• Getting it to evaluate instead of printing is honestly not a lot of code.
• Start by testing it with simple cases like 3 + 4. Don’t go for the gold at first.

Finish this first section before moving onto error checking. Programs are like houses: you need a good foundation. Don’t skip steps if you run into trouble. It’s better to get a solid understanding of the algorithm and get a 70 than try to attempt everything, do poorly, and get a 50.

Error checking [30 points]

Now, your program should be able to evaluate correctly-formatted expressions, but people make mistakes. Right now, your program might crash if you write something like 4 + . That’s no good!

Change your code to detect problems like this and throw ExpressionError with descriptive error messages. Try everything! Try giving your expression evaluator complete garbage and see what it does! It should never crash.

Hints

• Some stack operations can throw an exception. Don’t let them.
• Avoid these by checking if the stack is empty first, and throwing an ExpressionError instead.
• Keep track of the “last seen token”.
• You’ll have to add a variable to the class, and set it at the end of your handle methods.
• Then whenever you handle a new token, you can make sure that it’s OK.
• This will let you detect things like:
• two operators in a row
• two operands in a row
• empty brackets
• an operator right before or after a bracket
• etc.
• Be sure to test all possible bracket issues.
• Missing open brackets…
• Missing close brackets…
• Mismatched brackets…
• Think about when each of these things will occur.

Extra credit [+10 points]

You can earn up to 10 points of extra credit. If you do any extra credit, please follow the submission instructions for it below.

Here are some suggestions:

• Support more names by allowing the user to define names on the command line, like:

  > java InfixExpressionEvaluator beef=10
Enter infix expression: beef * 2
20.0

• They should be able to define as many names as they want.
• Look into Map.
• Detect semantic errors - errors in meaning.
• Divide-by-zero?
• Results that are too big to be represented (infinities)?
• Allow more features.
• Hexadecimal numbers, like 0xDC04?
• More operators?
• Check precedence/associativity tables for e.g. Java to get the right precedences.
• Trig functions, like sin(pi)?
• Negation, like -(4 * 5)?

Testing

We will be testing your code on the command line. You are welcome to use an IDE, but before submitting, please test that your Java files can be compiled and run on the command line without it.

DO NOT TURN IN CODE THAT DOES NOT COMPILE.

This is not acceptable in this class or in your following classes. Comment out the code that doesn’t compile and put comments at the top of your Java files for the grader. You may receive some partial credit for such code.

Code that crashes may also receive partial credit.

Submission

You will submit a ZIP file named username_proj2.zip where username is your Pitt username.

Do not put a folder in the zip file, just the following file(s):

• InfixExpressionEvaluator.java
• And if you did extra credit, please include a plain text (.txt) file named readme.txt that explains what you did for extra credit and how the grader should test it.

Do not submit any IDE project files.