Computer Science Courses

COMP2100

Related sites

COMP 2100/2500/6442: Lab 7 - Trees, Expressions and Parsing

This lab does not require you to create an Android app or program in Android Studio. Please write all code in Java using any editor or IDE of your choice.

Pre-lab Tasks - Expression Tree [1 mark]

This lab involves creating a simple prefix expression calculator program. The pre-lab task will involve creating the data structure for storing and evaluating the expressions for the calculator.

A prefix expression requires that all the operators precede the two operands they work on. For e.g. an infix expression x + y may also be represented in prefix form i.e. + x y.

The prefix calculator is required to support the following operations using float values:

• + - addition,
• - - subtraction,
• * - multiplication
• / - division

A simple grammar for prefix expressions to be evaluated by the calculator is:

    <exp> ::= <number> | <binop> <exp> <exp>    <binop> ::= + | - | * | / 

Create a number of classes that will enable you to represent and evaluate such expressions. Do this using inheritance of the following abstract class:

public abstract class Expression {    /*  This method prints an expression as a string         (which could be parsed back into a expression) */    public abstract String show();     /* This method evaluates the expression */    public abstract float evaluate();     static public Expression parse(String str) {        /*  Add code that will parse the string             creating the expression for that string */        /*  This is a place holder in order to get show             and evaluate working first */        return null;     }}

You are free to name/structure these classes as you see fit.

Once these classes are created, you should be able to construct different expressions. For e.g. the expression (+ 4.0 6.5) could be constructed with:

  Expression exp = new Addition(new Number(4.0), new Number(6.5)));

And then evaluated and shown using:

  float value = exp.evaluate();  System.out.println(exp.show() + " evaluates to " + value); 

from which we would expect the output:

   (+ 4.0 6.5) evaluates to 10.5

Assignment Checkpoint [1 mark]

To obtain this assignment check point mark you need to have started the assignment and at a minimum completed the following tasks BEFORE attending the lab session:

• Read over the assignment 2 specification
• Set up a gitlab project for the assignment (on gitlab.cecs.anu.edu.au) adding both the lecturers and your tutor as "Reporter"
• Created a plan to distribute work between members of your assignment group, documented this plan in your project wiki and added preliminary milestones in gitlab

Demonstrate these to your tutor while the pre-lab tasks are evaluated.

In-class activity - Expression Parsing [2 marks]

This may be implemented along with your assignment group member or individually as you prefer.

Complete the following tasks:

• Create a tokenizer and parser which will enable you to implement the evaluation of prefix expressions. The tokenizer must provide tokens to the parser
• Implement the parse method within the Expression class
• Create a program that works as a simple calculator which accepts a prefix expression as input from stdin. The program must parse this expression into an expression tree, evaluate it, and then output the result to stdout (i.e the terminal). No GUI is required

Updated:  25 April 2016 / Responsible Officer:   JavaScript must be enabled to display this email address. / Page Contact:   JavaScript must be enabled to display this email address. / Powered by: Snorkel 1.4

+61 2 6125 5111
The Australian National University, Canberra
CRICOS Provider : 00120C
ABN : 52 234 063 906