CS 261 Lab F - Expression Parsing

Due Wed Feb 25 at 9:00am

Overview

In this assignment, you will write a simple class that can parse and evaluate mathematical expressions represented as Strings, such as: 1 + 2 - (3 * 4). Such evaluation is an effective and common use of a Stack data structure--indeed, many computer languages and compilers use Stacks for this purpose!

This lab will be completed in pairs. Review the pair programming guidelines if you don't remember them!

Objectives

To practice working with Stacks
To become familiar with postfix notation

Necessary Files

You will want to download the copy of the zipped source files. and import them into Eclipse. These files include a number of helpful classes for you to use:

The Tokenizer class includes a static method, tokenize(), that will take a mathematical expression String and split it apart into an array of "tokens"--individual components of the expression.
- Components include the numbers (operands) of the expression, the operations (e.g.: +, -, *), and other systems such as parentheses. For example:
```
"1 + 2 - (3 * 4)"
```
  will be tokenized into the array
```
{"1", "+", "2", "-", "(", "3", "*", "4", ")"}
```
The ExpressionSyntaxException is a custom Exception you can throw if there is a syntax error (e.g., someone tries to use "3+*4)/12" as an expression).
A ExpressionTester that you can use to help get started testing your program. Note that you should also include other test cases (remember to incude all your test cases when you turn in your program!), and may want to use other debugging strategies as well. The debugger can be very handy for this!

This assignment draws heavily from the Koffman and Wolfgang textbook, particularly Chapter 3.4. Indeed, you will be implementing a version of the program described in that section. I highly suggest you have the book handy and use it as a reference :)

Infix, Prefix, and Postfix Notation

Normally we write mathematical expressions using what is called infix notation. We put the operator (e.g., the plus or multiplication sign) in between the operands (the numbers we want to add or multiply). So if we want to add 3 and 4, we write (3 + 4).

This is not the only way of writing mathematical expressions! Alternatively, we could use prefix notation (also called "Polish notation") and write an expression by putting the operator before the operands: if we wanted to add 3 and 4, we would write (+ 3 4). You can think of this kind of like having the operator be the "method" that we're calling, followed by the "parameters"---a variation on writing add(3,4). Indeed, some computer languages (called functional languages) work in exactly this way!

Finally, we could write mathematical expressions using postfix notation (also called "Reverse Polish Notation", or RPN), putting the operator after the operands: adding 3 and 4 is written as (3 4 +). This method of writing expressions makes them very easy to evaluate using a computer and a Stack--and is in fact how many computer systems process mathematics. Note that postfix notation doesn't require any further steps to keep operations in order--no parentheses are needed!

There are more details about these different notations following the above links, in the textbook, and we will talk about them briefly before lab. You can also see this link for a further set of examples.

Assignment Details

Your assignment is to create a ExpressionParser class that is able to evaluate mathematical expressions written in either postfix or infix notation. The class will be able to handle a number of binary operations: addition (+), subtraction (-), multiplication (*), division (/), and exponents (^). The class will be able to handle numbers in double precision, though does not need to handle negative numbers (parsing negative numbers is really hard!) Your program will also be able to handle parentheses, using those to make sure operations happen in order.

Furthermore, your ExpressionParser will be able to handle mathematical variables (eg., x and y)--the user can assign values to these variables, which will be used when the expression is evaluated. So if I assign 4 to x, I should be able to enter "x*(3+2)" and get a result of 20 back.

Read through these instructions carefully, they contain details about how to complete this program!

The `ExpressionParser`

Your ExpressionParser should be an ADT-style class--that is, one with attributes and constructors and such. The reason we're including a constructor is because your Parser will also need to store the values assigned to "user variables" x and y (you are only required to support these two variables).

Your parser must support the following public interface:

public double evaluatePostfix(String expression) //evaluates an expression in Postfix notation, returning the result
public double evaluateInfix(String expression) //evaluates an expression in Infix notation, returning the result
public void setXValue(double x) //sets the parser's "x" variable
public void setYValue(double y) //sets the parser's "y" variable

Postfix Evaluation

Your first step should be to write the method to evaluate postfix expressions. This is a relatively straightforward algorithm using a Stack.

The basic idea is read through the tokens of the expression (which you can get using the Tokenizer.tokenize() method). You add any operands (numbers) to hit to a Stack. Whenever you hit an operator, pop two numbers (left-hand side and right-hand side) off the stack, evaluate them (apply the operator), and push the result back on the stack for the next operator. Once you're done with the expression, pop the (last) number off the Stack, and that's your answer!

To sum up, the algorithm looks like:
```
for each token in the expression
  if the token is a number
    push it onto the stack
  else
    pop two numbers off the stack
    apply the operator
    push the result back onto the stack
return the top item from the stack
```
This algorithm will require you to use a Stack to store the operators. You should just use the built-in java.util.Stack class for this application. Note that you will be storing numbers in double precision.
You can convert a String (such as a token) into a double using the static Double.parseDouble() method.
- Helpful tip: this method will throw a NumberFormatException if the String cannot be converted. Thus you can use a try/catch block to check if a number can be converted, and if it can't (and it throws an Exception), then you know that the String must not be a number (and as such, would be an operator). This is one of the few ways that you can legitimately use try/catch and an expected exception to perform program logic.
Note that if the tokens are not numbers but are either "x" or "y", then that means that they are user-defined variables. You should place the appropriate value on the operand stack in their place.
You should strongly consider making a helper method (e.g., applyOperation()) that does the logic of deciding what math to do given a particular String operator. Note that you can most easily do this using a medium-sized if/else block. You might have this methods take the operator and the operand stack as parameters.
Be sure and test this method using the tester!

Infix Evaluation

Now that you've gotten the hand of expression evaluation and using a stack, you should implement infix evaluation. This is a significantly more complicated, but still doable.

There are a number of pieces that come into play with this algorithm--all of which are detailed in the textbook. Note that the textbook discusses how to convert from infix format to postfix format, with the expectation of then evaluating the postfix expression using the previous method. Your class should cut out the middle-man--evaluating the infix expression directly in this method (though you will be implicitly converting it to postfix so that you can use the operands stack).
You'll need to be able to handle the fact that infix notation requires operator precedence--that is, the fact that multiplication has a higher precedence than addition. So in the equation 3 + 4 * 5 - 6, we'd like to apply the multiplication before the addition and subtraction. What we will do is store all the "higher precedence" operators, then when we hit a lower-precedence operator, we'll apply all the higher ones first before applying the lower one. The best way to store the operators will be on another Stack! This way you can apply all the higher-precedence operators first, as well as store sequences of operators that may appear within parentheses.

Thus your algorithm will work as follows (again, this is detailed in the textbook)

01. for each token in the expression
02.   if it is an operand
03.     push it on the operand stack
04.   else if it is an operator
05.     if the operator stack is empty
06.       push the operator onto the stack
07.     else //this section is the "processOperator()" helper method in the text
08.       peek at the top of the stack
09.       if precedence of the current > precedence of the top
10.         push the current operator onto the stack
11.       else
12.         while the stack isn't empty and precedence of the current <= precedence of the top
13.           pop off the top operator
14.           apply this operator to the operands (on the operand stack)
15.           peek at the top operator and get its precedence for next time through the loop
16.         push the current operator onto the stack in preparation of the next token
17. for each operator left in the stack
18.   apply these operators to the operands on the stack (as normal)

This may look complicated, but is just a sequence of checks and loops using the stack. Try implementing it and printing out the Stacks (or tracing them with the debugger) to see what happens!

You will need to have some way of picking what operators have what precedence. The easiest way to do this is to create an array of ints that give each operator a number. For example, if you order the operators "+-*/", then you might have an array:
```
int[] PRECEDENCE = {1, 1, 2, 2};
```
If you store the list of operators in a String:
```
String OPERATORS = "+-*/";
```
Then you can use the indexOf() method on this String to get an index of an operator, which will be the index you can use to get the PRECEDENCE number. For example:
```
PRECEDENCE[OPERATORS.indexOf("*")]
```
will give you the precedence value (2) of multiplication (*).
If an operator isn't on your approved list, you should throw an ExpressionSyntaxException. Use the constructor that takes in a String as a parameter, so you can pass a message explaining what the syntax error is! (e.g., "____ is not a valid operator").

You will also need to handle parentheses. These add a further level of complication--but not too much of one. You'll need to make a couple of changes (again, detailed in the textbook)
1. You need to always push an open parentheses "(" onto the Stack when you first encounter it. You can do this where you previously checked if the Stack was empty (step 05).
2. When popping off operations to apply (step 13), if the operation you popped is a "(" (that you had stored on the Stack), then that means you've finished applying the operations within the parentheses, so will want to break out of the loop. You can set a sentinel boolean to use, or just use the break keyword to instantly "jump out" of the loop.
3. Finally, when you push the current token onto the operator Stack (step 16), you should be sure to not do so if the current token is a close paren (")")--since you will have already used it to indicate a need to pop off higher precedence operators!
- You should give the parentheses operators a precedence of -1; that way they will always have "lower" precedence than any other operators
- You When popping off the last operators from the stack, if you come across an open parentheses that is still on the stack, throw an Exception because there is a parentheses that cannot be closed!

Testing

As always, be sure and test your code thoroughly to make sure you understand the algorithm at play. Use lots of print statements and inspections to follow what is going on. You want to be able to explain how to use Stacks to evaluate infix expressions!

Be sure and add at least a few tests to the provided ExpressionTester that show you've tested your work.

Submitting

Make sure both your names are on all the classes you've modified (ExpressionParser and ExpressionTester), and upload the entire project directory to the LabF submission folder on hedwig. Only one partner should upload the code. Make sure you upload your work to the correct folder! The lab is due at the start of class the morning after lab.

After you have submitted your solution, log onto Moodle and submit the Lab F Partner Evaluation. Both partners need to submit evaluations.

Extensions

There are plenty of extensions to add to this, though no extra credit this time.

Try adding support for unary operators--that is, operators that work on only one operand instead of two. For example, can you support sqrt, sin, and cos?
Add suport for expressions in prefix notation. This will involve further research into how to convert from prefix to either infix or postfix.
It might be fun to make a little launcher class that uses the Scanner to allow the user to type in equations to be evaluated, like a calculator!
I know I always say this, but a very slick extension to this program would be to add a graphical component. For example, you might repeatedly evaluate an expression with different values for x (say, ranging from -10 to 10 with increments of .01). You can then take those points and plot them on a graph. Voila--you've created a graphing calculator!

Grading

This assignment will be graded based on approximately the following criteria:

A ExpressionParser class with the appropriate public interface [5%]
Your parser can evaluate expressions in postfix notation [20%]
Your parser supports all the required operations: +, -, *, /, ^ [5%]
Your parser supports user-defined variables x and y [10%]
Your parser can evaluate expressions in infix notation [25%]
Your parser handles parentheses in infix notation [15%]
Your parser throws ExpressionSyntaxExceptions when appropriate [5%]
ExpressionTester contains further test cases [10%]
You completed your lab partner evaluation [5%]