COMP 15 Project #8: Draw expression tree

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

Overview

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:

• Opens the file with the prefix expression,
• Builds a binary tree representation of the prefix expression while reading the expression from the file,
• Opens the PostScript output file, and
• Generates PostScript into the output file while traversing the tree.

Objectives

The objectives for this project are:

• To construct a program to display an expression tree using PostScript.
• To gain further experience with tree traversal.
• To improve practical skills with recursion.
• To gain further experience with software reuse.

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

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.

• The interior nodes, which are the operator nodes, should be drawn as filled circles (discs.)
• The leaf nodes, which are the name and numeric operands, should be drawn as filled rectangles (boxes.)
• A line should be drawn from each interior node to each of its children.

Here are some additional requirements to be satisfied:

• You must use a recursive algorithm to traverse the tree and generate PostScript. Please adhere to good programming practice:
  • Define a public function, draw, to draw the tree.
  • Define one or more private recursive functions to traverse the tree and generate PostScript.
  • Pass in a pointer to each subtree to be traversed.
  • Do not use global variables or data members to implement or assist traversal.
• You must use and provide a makefile to build your solution.
• You should thoroughly and systematically test the program.

Prefix expressions

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

    (min + max) / 2

    (div (add min max) 2)

    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

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

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:

• The x-position is equal to the number of nodes visited before the current node in the inorder traversal.
• The y-position is equal to the depth of the current node in the tree.

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

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) ;

The function show displays text at an x,y position, e.g.,

    psf.show(144, 144, "A string") ;

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
    ---------   ------------------------------------
    expr5.ps    (add (abs 10) (mul 30 (sub 10 xyz)))
    expr5.pdf   (add (abs 10) (mul 30 (sub 10 xyz)))
    expr7.ps    (sqrt (add (sub x2 x1) (sub y2 y1)))
    expr7.pdf   (sqrt (add (sub x2 x1) (sub y2 y1)))

http://www.eecs.tufts.edu/comp/15/notes/prefix

Submitting your work

Use the provide system to submit your finished program:

    provide comp15 a8 makefile prefix_draw.h ...

    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