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 objectives for this project are:
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 functionThe 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.
Here are some additional requirements to be satisfied:
Prefix expressions place operators in front of their operands. For example, the infix expression using conventional arithmetic operators:
(min + max) / 2is 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 UnaryOperands may be either names (e.g., min, max) or positive integer numbers.
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 fileYou 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.
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:
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.
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 textYou 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.,
psf.show(144, 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.
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.
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)))A note on the prefix parser is available at:
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 functionBe sure to build and test your program on comp15.cs.tufts.edu before submitting your work. This system is the target build and test platform for all course projects. Copyright © 2004-2013 Paul J. Drongowski