COMP 15 Project #8: Draw expression tree

COMP15 Fall 20XX
Due: Thursday, December 2, 11:00PM


The goal of this project is a program to generate a PostScript file that displays an expression tree. The program takes two command line arguments: the name of the file containing a prefix expression and the name of the PostScript file to be generated. The program performs the following steps:

The tree display algorithm (given below) can be used as the basis for the program, although you're free to experiment with algorithms of your own.


The objectives for this project are:

Lexical analyzer, prefix parser and PostScript file classes are provided as a foundation for your program.

What needs to be done

The following files are provided:

    makefile               Makefile to build the program
    lexan.h                Lexical analyzer class declaration
    lexan.cpp              Lexical analyzer functions
    psfile.h               PostScript file class declaration
    psfile.cpp             PostScript file class implementation
    prefix_draw.h          Class declaration for prefix parser/draw
    prefix_draw.cpp        Prefix parser and draw functions
    prefix_draw_main.cpp   Main function
The files are available in the directory /g/15/class/project8. You will need to copy these files to your own working directory and use them as a starting point for development.

When the expression tree is drawn, it should correctly show the shape of the tree. The root should be drawn near the top of the page and the rest of the tree should "grow" down the page.

Nodes should be labelled with the appropriate text -- the operator name, operand name or number. Labels do not need to be centered, but should appear next to the associated node. (Please keep it simple as the time to deadline is short.) The PostScript file class has been extended with functions to select a font, draw text, draw a disc (filled circle) and draw a box (filled rectangle.)

Here are some additional requirements to be satisfied:

Add comments to the source code to describe your approach and solution. Don't forget to fill out any header comments with your name, section and e-mail address.

Prefix expressions

Prefix expressions place operators in front of their operands. For example, the infix expression using conventional arithmetic operators:

    (min + max) / 2
is written as:
    (div (add min max) 2)
in prefix notation using symbolic operator names. Supported symbolic operator names are:
    Name   Operation             Arity
    ----   -------------------   -------
    add    Addition              Binary
    sub    Subtraction           Binary
    mul    Multiplication        Binary
    div    Division              Binary
    rem    Remainder (modulus)   Binary
    abs    Absolute value        Unary
    neg    Negative value        Unary
    sqrt   Square root           Unary
Operands may be either names (e.g., min, max) or positive integer numbers.

The Prefix class

Your efforts should focus on the Prefix and Node classes. (See the files prefix_draw.h and prefix_draw.cpp for the source code.) The Prefix class has five public method functions:

    bool open(char *filename)   Open the expression file
    void close()                Close the expression file
    bool parse()                Parse the expression in the file
    void print()                Print in prefix form
    void draw(char *filename)   Draw expression tree to PostScript file
You will need to complete the draw method function. You will also need to define recursive "inner" functions to traverse an expression and generate PostScript. You may add other private method functions.

The tree that is produced by the prefix parser consists of interconnected Node objects. The left and right subtrees are populated for binary operators. Only the right subtree is populated for unary operators. Please note that an instance of the Node class includes two data members, x and y, that may be used to retain the position of the node on the page. Feel free to add other data members to Node.

Drawing the expression tree

You may use the method suggested by Goodrich and Tamassia. In their method, a binary tree is drawn by performing an inorder traversal. The tree is drawn on a grid where the origin of the grid is located in the upper left corner of the page. Each node in the tree is assigned an x,y position using these two rules:

You will need to position and scale the nodes (and other graphic elements) in accordance with PostScript's coordinate system.

It is possible to draw a reasonable representation of a tree in one pass (a single traversal) of the tree. However, more sophisticated scaling, etc. may require two passes: one pass to determine the height and width of the tree and a second pass to actually generate the PostScript. The choice is yours.

Postscript file class

The PostScript file class has been extended with some new functions. Here is a brief summary of the public functions that form the PostscriptFile application program interface (API:)

  initgraphics()                             Reset the graphics state
  showpage()                                 Show current page
  gsave()                                    Save graphics state
  grestore()                                 Restore graphics state
  scale(double sx, double sy)                Scale
  rotate(double angle)                       Rotate
  translate(int tx, int ty)                  Translate
  line(int x1, int y1, int x2, int y2)       Draw line
  rect(int x, int y, int width, int height)  Draw rectangle
  box(int x, int y, int width, int height)   Draw box (filled rectangle)
  circle(int x, int y, int radius)           Draw circle
  disc(int x, int y, int radius)             Draw disc (filled circle)
  setgray(double gray)                       Set fill gray level
  font(char *key, double scale)              Select and scale font
  show(int x, int y, char *text)             Draw text
You are welcome to add new functions, but this is purely optional. Naturally, any changes must build and behave correctly.

The functions box and disc are similar to the rect and circle functions, respectively. They produce filled figures instead of an "outline."

The setgray function sets the fill color. The parameter specifies the gray level where 0.0 is black and 1.0 is white.

The font function selects a font and makes it the current font in the PostScript graphics state. The first argument is a font name that selects the desired font and the second argument is the scale. Here is a simple example:

    psf.font("Times-Roman", 12.0) ;
where psf is a PostscriptFile object.

The function show displays text at an x,y position, e.g.,, 144, "A string") ;
The x-position is the left end of the text string. The y-position is the baseline of the text string. Left and right parenthesis characters are not allowed in the text string unless they are preceded by two backslash (\\) escape characters.

Converting a number to ASCII

At some point, the program will need to convert the internal binary representation of a number operand to a formatted ASCII string. Properly, one should use a library function such as sprintf to do this job. (The sprintf function is defined in the C standard I/O library, cstdio.) A non-standard function, itod, has been provided in prefix_draw.cpp to perform the conversion as well. Either approach is acceptable for this assignment.

The function itod is recursive and you might want to study it's implementation. It's a classic example of a recursive string operation.

On-line resources

Sample output files are available in the /g/class/project8 directory:

    File        Expression
    ---------   ------------------------------------    (add (abs 10) (mul 30 (sub 10 xyz)))
    expr5.pdf   (add (abs 10) (mul 30 (sub 10 xyz)))    (sqrt (add (sub x2 x1) (sub y2 y1)))
    expr7.pdf   (sqrt (add (sub x2 x1) (sub y2 y1)))
A note on the prefix parser is available at:

Submitting your work

Use the provide system to submit your finished program:

    provide comp15 a8 makefile prefix_draw.h ...
The files to be submitted are:
    makefile               Makefile to build the program
    lexan.h                Lexical analyzer class declaration
    lexan.cpp              Lexical analyzer functions
    psfile.h               PostScript file class declaration
    psfile.cpp             PostScript file class implementation
    prefix_draw.h          Class declaration for prefix parser/draw
    prefix_draw.cpp        Prefix parser and draw functions
    prefix_draw_main.cpp   Main function

Be sure to build and test your program on before submitting your work. This system is the target build and test platform for all course projects.

Copyright © 2004-2013 Paul J. Drongowski