CS0445 Project 2: Expression evaluation Solved

Download and extract these materials. Contained are:

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] ¶
If you don’t have the book… ask your classmates.

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)?