[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]

COMP2100/2500
Lab 2: Expression Parser and Evaluator

Summary

You will work on a program that uses a recursive data structure: an expression parser and evaluator. This uses Expression Version 3 from Lecture 8. It has a lot in common with the XML parser and processor you will be working on in the project.

Aims

• To give you practical experience building and traversing recursive data structures.

• To give you some familiarity with the architecture of the project.

Preparation

Read through your lecture notes from Lecture 7, Lecture 8 and Lecture 9 on Recursive Data Structures.

Before the lab, work through (or at least read) the stack-based calculator exercises. If you can't complete them before the lab, make sure you come back to them later.

---

Exercise 1. Getting started

Download and unpack the Jar file ExpressionParser.jar.

Like the stack-based calculator, this program deals with simple integer expressions. That program evaluated expressions using a stack. This program reads expressions written in ordinary algebraic notation, and stores them in a tree structure. It can then print them out and evaluate them. It uses Expression Version 3 from Lecture 9.

We will use the expressions (1 + 2) * 3 and 1 + (2 * 3) as examples. These expressions are represented as:

         *             +
        / \           / \
       +   3         1   *
      / \               / \
     1   2             2   3

The program will only accept expressions which satisfy a very simple grammar. The rules are:

In other words, an expression consists either of a single term, or two terms separated by one of the four binary operators; a term consists either of an expression in parentheses, or a constant; and a constant consists of a string of one or more digits. The only characters allowed are digits, the four operators, and parentheses. Spaces are also allowed, but are ignored. Parentheses are compulsory around every sub-expression, even when the normal rules of arithmetic say you don't need them.

Before you run the program, take a minute to follow the two example expressions through the grammar above, and see how they give rise to the tree structures pictured.

Also take a few minutes to read through the code. The classes representing expressions should be familiar to you from the lectures, but the rest of the program is new. The Lexer breaks expression strings into tokens, meaningful items of data like parentheses, arithmetic operators and numbers. The Parser uses the grammar above to turn that stream of tokens into a tree.

Now compile and run the program. It should work with either Java 1.4.2 or 1.5. The root class is Calculator. Try entering one of the example expressions above, and see what the other commands do. Remember to read the instructions carefully. You have to enter a new expression with the ‘n’ command before you can do anything interesting.

You will discover that the program doesn't yet do what it is supposed to. In fact, the evaluation feature, subtraction and division operations, and the pre- and post-order printing operations have not yet been implemented.

Your first task is to implement the ‘v’ command which evaluates the current expression. Where should this be implemented? Look at the code and work it out. (Try to do this without looking back at your lecture notes.)

When you run the program on the two example expressions, the output should look like this (but it won't until you complete this exercise because the ‘v’ command almost always returns zero):

> n (1+2)*3                     > n 1+(2*3)
> i                             > i
In-order : ((1 + 2) * 3)        In-order : (1 + (2 * 3))
> v                             > v
Value = 9                       Value = 7

Having done that, add subtraction and division expressions to the system. This will mean adding two new sub-classes of class Expression and also making some minor modifications to some of the other classes, like Parser. When you implement class Division you will need to think about what to do if the user tries to divide by zero.

---

Exercise 2. Pre- and Post-order printing

Add new features which enable the calculator to print expressions in pre-order and post-order, as well as the standard ‘in-order’ or ‘infix’ form.

In pre-order, you print the operation, then the two expressions it should operate on. This is like thinking of the arithmetic operations as functions with two arguments.

In post-order, or reverse Polish notation, you print the two sub-expressions, then the operator. This is the way the stack-based calculator works.

Here are our two example expressions printed in all three orders:

In-order: (1 + 2) * 3            In-order: 1 + (2 * 3)
Pre-order: product(sum(1,2),3)   Pre-order: sum(1,product(2,3))
Post-order: 1 2 + 3 *            Post-order: 1 2 3 * +

---

Exercise 3. The Visitor pattern

Refactor your code using the design of Expression Version 4, with the Visitor pattern. You will hardly need to add any new code; it's more a matter of reorganising the existing code.

This exercise is particularly important, because this is the same style of implementation as is used in the project software that you will be working on in the assignments.

---

*Exercise 4. Order of operations

Starred exercises are extension work. You do not have to complete them. They may be significantly more difficult than the other exercises.

We shouldn't really have to put parentheses in an expression like 1+(2*3), since the rules of arithmetic say that the multiplication should be done first anyway. Rewrite the grammar for our parser so that the precedence is built in, and parentheses are only needed where mathematics says they're needed. Now rewrite the parser to reflect this change. While you're at it, you might want to think about allowing negation as well.

Hint: You will need a new syntactic element. The usual name for this is a Factor. Roughly, an Expression is a sum or difference of Terms; a Term is a product or quotient of Factors, and a Factor is either a Constant or an Expression in parentheses.

[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]