CSSE 230
Expression Evaluator Programming Assignment  - 60 Points

Overview

Programming languages must evaluate expressions following the syntax of the language. In this assignment, you will write a tool that will evaluate simple mathematical expressions given in different forms like 8 + 7 * 5 (infix) and 8 7 5 + *  (postfix).

Starting code is in the Evaluator project in your pair's repository (see link from schedule page for your team number). Commit your working code to the repository.

Objectives

• Develop practical algorithms that require a stack.

Detailed specifications

You are used to evaluating mathematical expressions that are written using infix notation, that is, each operator appears between the operands (numbers), such as

4 * 5

6 * ( 10 - 7 ).

4 5 *

6 10 7 - *,

Postfix notation has two advantages over infix notation. First, the order of operations is unambiguous without requiring parentheses. As we will see, 3 + ( 4 * 5 ) can be written as 3 4 5 * + , while ( 3 + 4 ) * 5 can be written as 3 4 + 5 *. Second, computers can evaluate postfix expressions easily using a stack.

In the very first example above, you can save the operands (4 and 5) on a stack and when you finally read an operator, just pop two operands and apply the operator. The second example works similarly - push the three operands (6, 10, and 7). When you read the - sign, pop the top two operands (7 and 10), apply the -, then push the answer back. When you read the * sign, pop the top two (3 and 6) and apply the * and push the answer. When you reach the end of the input, pop the answer. Your stack should now be empty - if not, the expression was malformed (too many operands). You can also detect if there were too many operators - can you see how?

Of course, calculators and computers don't require you to enter your expressions in postfix - they do it for you. Surprisingly, there is an algorithm to convert infix expressions to postfix that also uses a stack. Hint: in this postfix to infix conversion algorithm, the stack holds operators, not operands. If you try a couple examples, you'll see that this makes sense, since the order of the operands doesn't change, but the operators must somehow be stored and moved later in the output string.

So to evaluate infix, just convert it to postfix, then apply the algorithm described above!

Your starting code includes an abstract class called Evaluator, that has an abstract method to evaluate strings and return an int. You will write PostfixEvaluator and InfixEvaluator subclasses in which you will override this method. This is not the only way to do this, but is good extensible, object-oriented design. (Perhaps we might want to write a PrefixEvaluator later, who knows?)

We want you to use the infixToPostfix conversion algorithm as the first step of evaluating infix expressions, so the tests include specific tests to isolate that method. Note that this method takes a String argument and returns a String.

Hint: The starting code has errors. I tried to make it so that using Eclipse to fix the errors in the Main class will give you stubs of the classes and methods. It should even guess that InfixEvaluator should extend Evaluator and that the return type of infixToPostfix should be a String. If not, you can make these adjustments. You'll also need to add your own comments.

Requirements

1. Your algorithm must work in linear time with respect to the number of tokens (operators and operands). Thus, you may only read through the String once and build up the output string once using a loop - no backtracking or inserting output into arbitrary elements in the input string. This also means we must build up the output using a StringBuilder, not a String - see the javadoc for StringBuilder for examples of how to use it if you haven't.
2. Both algorithms must use a stack.
3. Neither algorithm can use recursion - recursion does use a stack internally, but we want the use of the stack to be explicit here.
4. Both algorithms must handle the four basic operators (+, -, *, and /), plus exponents (^).
5. For full credit, you must be able to handle parentheses in infix expressions.
6. For full credit, you must throw ArithmeticExceptions when the input is malformed, as demonstrated in the tests.
7. You must write 3 additional unit tests for each method in the same format as mine. Please name them in such a way that the name tells what function is being tested (for good examples, see my InfixEvaluatorTest methods for correctly throwing Exceptions).

Simplifying Assumptions and Hints

1. You may assume the tokens (operators and operands) in the input strings are all separated by spaces, thus making it easy to use a Scanner to parse the String one token at a time.
2. You may assume that the only operands in the input will be non-negative integers.
3. All math will be integer math, thus you may drop remainders during division if they occur.
4. You may add whatever additional helper methods you need. For example, I added one to compare the precedence of the infix operators. 

Grading

Grades will be based on unit tests and programming style.

Note that the unit tests currently add up to significantly less than 60 points - you will be graded how well your unit tests cover cases I hadn't thought of, and on how well you pass some of your classmates' tests.

I reserve the right to change the point value of each unit test and the final point value of the assignment based on the number of good test cases I receive from the class.