[Lab 1] [Lab 2] [Lab 3] [Lab 4] [Lab 5] [Lab 6] [Lab 7] [Lab 8] [Lab 9] [Lab 10] [Lab 11]

COMP2100
Lab 4: Expression Parser and Evaluator

Summary

You will work on another program which uses a recursive data structure: an expression parser and evaluator. This uses EXPRESSION Version 3 from Lecture 9. 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 8, Lecture 9 and Lecture 10 on Recursive Data Structures.

---

Exercise 1. Getting the source code

Download, uncompress and unpack the compressed archive file lab04.tar.gz.

Like last week's program, this program deals with simple integer expressions. Last week's program evaluated expressions using a stack. This week's program uses expression trees.

Like last week, we will use the expressions (1 + 2) * 3 and 1 + (2 * 3) as examples. Using expression trees, these expressions would be represented as:

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

---

Exercise 2. Expression parser and evaluator

This program reads simple arithmetic expressions, in ordinary algebraic notation, and stores them in a tree structure. It can then print them out and evaluate them. It uses a structure like EXPRESSION Version 3 from Lecture 9.

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 look at 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.

Now compile the program. The root class is CALCULATOR and the starting routine is main, but you can save yourself some typing by using the Ace file provided. In this case you compile with the command:

compile calculator.ace

Now run the program from the command line by typing its name: ./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 and the subtraction and division operations have not been implemented.

Your first task is to implement the `v' command which evaluates the current expression. Where is this implemented? Look at the code and work it out.

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 and OPERATIONS. When you implement class DIVISION you will need to think about what to do if the user tries to divide by zero.

---

Exercise 3. 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 last week worked.

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 4. The Visitor Pattern

Rewrite the program from Exercise 3 using the design of EXPRESSION Version 4, with the Visitor pattern.

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 Assignment 2.

---

*Exercise 5. 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 program to reflect this change. While you're at it, you might want to think about allowing negation as well.

Hint: You will need another class to represent 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.

[Lab 1] [Lab 2] [Lab 3] [Lab 4] [Lab 5] [Lab 6] [Lab 7] [Lab 8] [Lab 9] [Lab 10] [Lab 11]