Problem #3: A Simple Graphics Language

1986 ACM East Central Regional Programming Contest

Problem #3: A Simple Graphics Language

This problem deals with a simple language to create graphical objects. The input to your program is a series of graphical "commands" and the output is a 20 row by 40 column array of characters that make up the final "picture".

The language consists of six commands the operate on a stack of picture objects. Objects are of type point, line (line segment), or rectangle. Associated with each object is a reference point, which defines a point on the object that is to be used when the object is referenced; and a location, which determines where in the picture the object (i.e., the reference point) is to be located. The reference point for each object is defined as follows:

point The reference point of a point is the point itself.

line The reference point of a line depends on its orientation. If the line is horizontal or diagonal, the reference point is the point with the smallest x-coordinate. If the line is vertical, the reference point is the point with the smallest y-coordinate.

rectangle The reference point of a rectangle is the lower left corner. Note that the rectangle may originally be defined in terms of any two diagonally opposite corners, given in either order.

The graphics commands are read from input, one per line, until end of file. The command is the first character on the line. As each line is read, the command is "executed" as follows:

p x y Create a point object with location (x, y) and push it on the stack. x is in columns 3 and 4; y is in columns 6 and 7

l Pop two points off the stack. Create a line object defined by these two points and push it on to the stack.

rc Pop two points off the stack. Create a rectangle defined by these two points and push it on to the stack. The fill-character (see below), which appears immediately following the r, is c.

m Pop a point and an arbitrary object off the stack (in that order). "Move" the location of the object to this point.

d Duplicate the object on top of the stack by popping it off and pushing it back on twice.

s Pop and "show" the object on the top of the stack by putting it into the character array the contains the picture. An object is placed into the array with its reference point at its location.

The show command pops an object from the stack and places it into the 20 by 40 character array, generally obscuring objects that lie beneath it. The picture is initially all blanks, and is printed at the end of input. Each object is drawn as follows:

point Points are invisible, so the show command on a point does not change the picture. A line whose endpoints coincide and a rectangle whose corners coincide are also invisible.
line Lines are only horizontal, vertical or of slope 1 or -1 (all lines drawn by the test data will be one of these types). Horizontal lines are drawn using the dash (-), vertical lines using the vertical bar (|) lines of slope 1 the slash (/), and lines of slope -1 the backslash (\).
rectangle The vertical and horizontal sides of rectangles are drawn with vertical bars and dashes, respectively; however a plus sing (+) is used at the corners of rectangles.
The interior of a rectangle is drawn using the fill character. If the fill character is non-blank, it is placed into every interior position of the rectangle. If the fill character is blank, the interior of the rectangle is left unchanged.
A rectangle may have either zero height or zero width and still be visible. It simply appears as a line with plus signs at either end. A rectangle with both zero heigth and zero width is an invisible point.

You may make the following assumptions:

The picture is defined so the lower left corner has coordinates x = 1 and y = 1, and the upper right corner has coordinates x = 40 and y = 20.
The input is both syntactically and semantically correct. All objects lie wholly within the 20 by 40 picture. For example, the x and y values in the p command satisify 1 <= x <= 40 and 1 <= y <= 20.
You may assume that there will never be more than 20 objects on the stack at one time

Sample Input

p  1  1
p 40 20
r 
s
p  5 10
p  8 14
r*
d
p 15 11
m
s
s
p 10  5
p 20  5
l
s
p 11 6
p 12 7
l s

Sample Output

+--------------------------------------+
|                                      |
|                                      |
|                                      |
|                                      |
|             +--+                     |
|   +--+      |**|                     |
|   |**|      |**|                     |
|   |**|      |**|                     |
|   |**|      +--+                     |
|   +--+                               |
|                                      |
|                                      |
|          /                           |
|         /                            |
|        -----------                   |
|                                      |
|                                      |
|                                      |
+--------------------------------------+

point	The reference point of a point is the point itself.
line	The reference point of a line depends on its orientation. If the line is horizontal or diagonal, the reference point is the point with the smallest x-coordinate. If the line is vertical, the reference point is the point with the smallest y-coordinate.
rectangle	The reference point of a rectangle is the lower left corner. Note that the rectangle may originally be defined in terms of any two diagonally opposite corners, given in either order.

p x y	Create a point object with location (x, y) and push it on the stack. x is in columns 3 and 4; y is in columns 6 and 7
l	Pop two points off the stack. Create a line object defined by these two points and push it on to the stack.
rc	Pop two points off the stack. Create a rectangle defined by these two points and push it on to the stack. The fill-character (see below), which appears immediately following the r, is c.
m	Pop a point and an arbitrary object off the stack (in that order). "Move" the location of the object to this point.
d	Duplicate the object on top of the stack by popping it off and pushing it back on twice.
s	Pop and "show" the object on the top of the stack by putting it into the character array the contains the picture. An object is placed into the array with its reference point at its location.