Assignment 4: “ArithmeticExpressions”

Thursday, October 17, 2002
Due: Tuesday, November 5, 2002

Previous page | Next page

Description

Write a program that

reads a fully parenthesized arithmetic expression,
attempts to simplify the expression, and then
outputs the (possibly simplified) expression
followed by assembly language code for computing its value.

Examples

Assume the input consists of fully parenthesized expressions built from single-digit integers, single-letter variables, and the operations +, -, and *.

Examples are

( ( x + 2 ) * ( x - 2 ) )
( x * ( x * x ) )
( ( 4 - 2 ) * 5 )
( ( 3 * ( x * x ) ) - ( 2 * ( y - 2 ) ) )
0
( 3 - ( ( x - y ) - ( x - y ) ) )

For the first of the above expressions the output needs to be

( ( x + 2 ) * ( x - 2 ) )
----------
LOAD X
LOAD 2
ADD
LOAD X
LOAD 2
SUBTRACT
MULT

(The idea is that this is machine code for a machine that has a stack in its hardware.)

For the last expression the output needs to be

3
----------
LOAD 3

No error checking

Assume that the input has no syntax errors and that the individual tokens are separated by whitespace (implying that you can read them simply with a cin >> ... ).

Simplifications to carry out

These need to be carried out on the whole expression as well as on each subexpression.

0 + f and f + 0 turn into f.
0 * f and f * 0 turn into 0.
1 * f and f * 1 turn into f.
f - f turns into 0.
An expression without variables is replaced by a single number, its value.

Grading guidelines

         Compiles without warnings:  5
                  Acceptable style:  5
Correctness ...
        read and parse expressions: 10
                   simplifications: 25 (5 points for each)
                   code generation: 15
                    -------------------
                            Total : 60

Files to turn in

There are four files altogether: expression.{h, cxx}, main.cxx and a Makefile.

Previous page | Next page | Back to top

3:40 PM, Thursday, December 12, 2002