Conforme descrito na publicação “The Algorithmic Beauty of Plants”, de Przemyslaw Prusinkiewicz e Aristid Lindenmayer, a estrutura de uma árvore pode ser representada por meio dos chamados Context-Free Lindenmayer Systems (ou simplesmente Sistemas-OL).
Vamos mostrar que a utilização de pilhas e recursões permite codificar Sistemas-OL deste tipo em simples sequências de caracteres (strings).
Tomemos a descrição de comandos de um sistema posicional típico (como o turtle), em que:
- "F" denota mover-se para frente;
- "+" denota virar à esquerda em "delta" graus;
- " - " denota virar à direita em "delta" graus;
- " [ " denota salvar a posição atual na pilha;
- " ] " denota retornar a última posição salva na pilha.
Considere, agora, a sequência de caracteres abaixo:
F[+F][-F[-F]F]F[+F][-F]
É fácil ver que essa sequência representa a estrutura em árvore da Figura 1.
Figura 1
Quando associado à recursão, esse tipo de codificação viabiliza a representação de estruturas aparentemente complexas a partir da concatenação de poucos caracteres. Isso porque, recursivamente, é possível repetir diversas vezes o mesmo padrão da estrutura da árvore em diferentes escalas dentro da cadeia recursiva.
Como vimos na Figura 1, muitas vezes é necessário retornar a uma posição anterior da árvore para que se possa construir um novo “galho”. Sabe-se que estruturas em pilhas permitem o armazenamento (push) e a posterior recuperação de informações sobre posições anteriores (pop). Portanto, a utilização de pilhas aparece como uma solução bastante interessante para construção de árvores em Sistemas-OL.
Vejamos, por exemplo, a Figura 1.24.b da publicação “The Algorithmic Beauty of Plants” (apresentada na Figura 2). Nossa intenção é reconstruir a representação em árvore a partir da tradução do código em caracteres.
Figura 2
Para tanto, primeiramente, importa-se a biblioteca “turtle”, que nos permitirá plotar a estrutura da árvore em um sistema posicional de duas dimensões.
# Class 3 Exercise 9f: create the tree representation shown in Figure 1.24.b of The Algorithmic Beauty of Plants
# (Przemyslaw Prusinkiewicz, Aristid Lindenmayer)
from turtle import * # imports Turtle library
Depois, definem-se duas funções e uma classe que serão essenciais para que possamos retornar a “ponta da caneta” para coordenadas que já tenham sido percorridas em etapas anteriores do processo de construção da árvore. Repare que na classe Stack (pilha), os métodos push e pop são definidos explicitamente.
def get_turtle_state(t_obj): # gets turtle's current heading (in degrees) and position (in (x,y) 2-D coordinates)
return t_obj.heading(), t_obj.position()
def set_turtle_state(t_obj, state): # sets turtle's heading (in degrees) and position (in (x,y) 2-D coordinates)
t_obj.setheading(state[0])
t_obj.setposition(state[1][0], state[1][1])
class Stack: # creates the Stack class
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item): # defines 'push' function explicitly
self.items.append(item)
def pop(self):
return self.items.pop() # defines 'pop' function explicitly
def peek(self):
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
Agora, constrói-se a função recursiva de geração dos galhos, para cada um dos níveis “n”, conforme indicação do código apresentado na Figura 2.
def build_branch_level_f(n): # defines outer level building process recursively
n = n - 1
if n >= 0: # while 'level' is greater than zero, do: (please refer to the process definition in Figure 1.24)
build_branch_level_f(n) # calls inner level building process
t_s.push(get_turtle_state(turtle)) # saves turtle's current position in the stack
turtle.left(delta) # left turn of delta degrees
build_branch_level_f(n) # calls inner level building process
turtle.penup() # sets pen's state to 'up' so that no line is drawn when returning to saved position
set_turtle_state(turtle, t_s.pop()) # return to saved position
turtle.pendown() # sets pen's state back to 'down'
build_branch_level_f(n) # calls inner level building process
t_s.push(get_turtle_state(turtle)) # saves turtle's current position in the stack
turtle.right(delta) # left turn of delta degrees
build_branch_level_f(n) # calls inner level building process
turtle.penup() # sets pen's state to 'up' so that no line is drawn when returning to saved position
set_turtle_state(turtle, t_s.pop()) # return to saved position
turtle.pendown() # sets pen's state back to 'down'
t_s.push(get_turtle_state(turtle)) # saves turtle's current position in the stack
build_branch_level_f(n) # calls inner level building process
turtle.penup() # sets pen's state to 'up' so that no line is drawn when returning to saved position
set_turtle_state(turtle, t_s.pop()) # return to saved position
turtle.pendown() # sets pen's state back to 'down'
else:
turtle.forward(8) # when the level is equal to zero, returns the forward process
Por fim, declaram-se os parâmetros "delta" e "n" (conforme orientações da Figura 2) e invoca-se a rotina.
turtle = Turtle() # creates turtle object of Turtle
t_s = Stack() # t_s (= turtle position stack) is an object of the class "Stack"
turtle.color('dark olive green', 'dark olive green') # tree-ish trace and fill colors
turtle.pensize(2) # adjust thickness to get a closer print of picture 1.24.b
level = 5 # number of steps
delta = 20 # tilt angle (in degrees)
turtle.penup() # sets pen's state to 'up' so that no line is drawn when returning to saved position
turtle.right(90) # takes turtle...
turtle.forward(260) # ...to the bottom of the drawing palette
turtle.left(180) # tilts 90 degrees (so that the turtle faces up at the beginning)
turtle.pendown() # sets pen's state back to 'down'
build_branch_level_f(level) # calls outer level building process
mainloop() # keeps palette on screen after the script is over
O resultado obtido (Figura 3) é bem similar àquele da Figura 2!
Figura 3