Programming Assignment 3 - Turtle Graphics

See the assignment turn-in page (last modified on 22 January 2002) for instructions on turning in your assignment.

The turtle crawls around according to the following commands:

1. F - move forward f units with the pen on the paper.

2. f - move forward f units with the pen off the paper.

3. + - rotate the turtle r degrees clockwise (to the right) about the pen.

4. - - rotate the turtle l degrees counterclockwise (to the left) about the pen.

The turtle's position is the (x, y) location of its pen and the direction its head is pointing. The turtle also has a position stack which it uses to remember positions; the position stack has infinite capacity. The turtle manipulates its position stack in response to two more commands:

1. [ - push the current position into the position stack. This command does not change the turtle's position.

2. ] - pop a position off the top of the state stack and set the turtle's position to be equal to the popped position. This command (usually) changes the turtle's position.

A sequence of turtle commands is known as a turtle string. Despite the suggestive names, it is not necessary for the [ and ] commands to match in a turtle string. However, the turtle should never try to pop an empty position stack. For example,

F [ F [ F

is a good turtle string even though the turtle never pops the position stack, while

F[F]]

is a bad turtle string because the turtle tries to pop the empty position stack (assuming the position stack was empty at the start of the string).

A turtle executes a turtle string by scanning the string from left to right and executing each command it finds. For example, when executed, the turtle string F + f - F causes the turtle to

The result of executing a turtle string is the drawing the turtle leaves behind. In the previous example, the result is

(the commands and turtles are not part of the drawing).

A turtle program has the following format

A turtle program executes as follows:

1. The start turtle string turtle-string_s is evolved through some number of generations to produce the final turtle string.

2. The turtle executes the final turtle string to produce a drawing.

A turtle string s is evolved from one generation to the next in the following way:

1. Each non-overlapping occurrence of the pattern turtle string turtle-string_p is marked in a left-to-right scan of s.

2. Each marked occurrence of turtle-string_p in s is replaced by the replacement turtle string turtle-string_r.

F + F + F
F + F -> F + F + [ F + F ]

the generation 0 turtle string is the start turtle string F + F + F. The generation 1 turtle string evolves from the generation 0 turtle string

F + F + F

by marking all non-overlapping occurrences of the pattern turtle string F+F from left to right:

F+F + F

and replacing the marked pattern turtle strings with the replacement turtle string F + F + [ F + F ]:

F+F+[F+F] + F

The generation 2 turtle string evolves from the the generation 1 turtle string

F + F + [ F + F ] + F

by marking all non-overlapping occurrences of the pattern turtle string F+F from left to right:

F+F + [ F+F ] + F

and replacing them with F + F + [ F + F ]:

F+F+[F+F] + [ F+F+[F+F] ] + F

and so on.

Drawing commands is a sequence of zero or more of the following commands:

1. draw n - Create an n-th generation turtle string and execute it. n is an non-negative integer.

   At the start of each draw command the turtle is positioned with its pen at the origin of a Cartesian coordinate system (increasing x to the right, increasing y up) with its head pointing up the positive Y axis (that is, at 90 degrees).

2. right = r - Sets the amount of clockwise rotation caused by a + command to r degrees. r is a floating point number; if r is less than zero, then the turtle rotates counter-clockwise.

3. left = l - Sets the amount of counter-clockwise rotation caused by a - command to l degrees. l is a floating point number; if l is less than zero, then the turtle rotates clockwise.

4. forward = f - Sets the number of units moved by a F or f to f units. f is a floating point number; if f is less than zero, then the turtle moves backward (that is in the direction opposite of forward).

The initial values are l = r = 20 degrees and f = 1 unit. Drawing commands may appear in any order. Each right, left, or forward command effects all subsequent draw commands until they are changed by a following right, left, or forward command. If a turtle program doesn't contain any draw commands, the program does nothing.

Input

Output

g++ -c -I/export/home/class/cs-509/pa3 your-file.cc