O que são árvores de expressão?
Árvores de expressão são representações hierárquicas de fórmulas matemáticas ou lógicas. Elas organizam operadores como nós internos e operandos como folhas terminais. Por exemplo, a expressão (3 + x) * 2 vira uma árvore com raiz em multiplicação. Cada nó interno executa uma operação sobre seus filhos esquerdo e direito. Folhas contêm variáveis, constantes ou funções sem argumentos. Essa estrutura é intuitiva e facilita a avaliação computacional passo a passo. Além disso, ela é a base da programação genética e de compiladores. Sua natureza recursiva permite manipulações simples como percurso em profundidade. Portanto, árvores de expressão são uma ponte entre sintaxe e semântica.
Como elas são construídas e avaliadas?
A construção começa com uma notação infixa, que é convertida para pré-fixa ou pós-fixa. Em seguida, um parser monta a árvore usando uma pilha de nós. A avaliação ocorre recursivamente: calcula-se o valor dos filhos primeiro. Depois, aplica-se o operador do nó raiz sobre esses valores parciais. Esse processo é determinístico e livre de ambiguidades, graças à hierarquia. Por exemplo, a árvore garante que a multiplicação precede a adição corretamente. Ela também pode ser simplificada usando regras algébricas durante a execução. Muitas linguagens, como Python, usam árvores de sintaxe abstrata (AST) internamente. Dessa forma, elas viabilizam a análise e transformação de código fonte.
Principais usos e vantagens
Árvores de expressão são amplamente empregadas em otimização de consultas SQL. Elas também são cruciais em sistemas de prova automática de teoremas. Na programação genética, cada indivíduo é uma árvore de expressão mutável. Sua principal vantagem é a interpretabilidade direta por seres humanos. Além disso, elas permitem derivação simbólica e simplificação algébrica automática. Outro uso é na compilação just-in-time (JIT) para gerar código eficiente. Elas facilitam a detecção de erros semânticos antes da execução final. Por fim, são essenciais para calculadoras gráficas e softwares educacionais.
A estrutura de uma árvore de expressão é definida por sua profundidade e tamanho. Profundidade é o caminho mais longo da raiz até uma folha qualquer. Tamanho é o número total de nós presentes na árvore inteira. Ambos os atributos influenciam a complexidade computacional da avaliação. Árvores muito profundas podem causar estouro de pilha em linguagens recursivas. Já árvores muito grandes tornam a busca evolutiva mais lenta e custosa. Por isso, técnicas de poda (pruning) são frequentemente aplicadas. Elas removem subárvores redundantes ou que não contribuem para o resultado. A poda melhora a generalização e reduz o overfitting em dados ruidosos. Outra operação comum é a normalização, que reorganiza nós para formas canônicas. Isso ajuda a comparar duas árvores estruturalmente diferentes, mas equivalentes. A serialização da árvore para string é trivial com percursos pré-ordem. Essa string pode ser armazenada ou transmitida facilmente entre sistemas. Portanto, árvores de expressão são versáteis e amplamente adotadas.
Um exemplo clássico é a avaliação de expressões aritméticas com variáveis. Considere a expressão: (x + 2) * (x – 1), onde x é uma entrada qualquer. Sua árvore terá raiz em multiplicação, com duas subárvores de adição e subtração. Para x=3, o valor é (3+2)*(3-1) = 5*2 = 10, calculado recursivamente. Esse mesmo princípio se aplica a funções trigonométricas, lógicas e booleanas. A seguir, apresento um enunciado prático com resolução em Python.
Enunciado do exemplo clássico
Crie uma classe em Python que represente uma árvore de expressão binária. Ela deve suportar os operadores +, -, *, / e a função seno (unária). As folhas podem ser constantes numéricas ou a variável simbólica ‘x’. Implemente um método que avalie a árvore para um dado valor de x. Também implemente um método que imprima a expressão em notação infixa com parênteses. Teste sua árvore com a expressão: (x + 1) * sin(x) – 2. Avalie para x = 0, 1, 2, 3 e 4 e plote os resultados. Gere também um gráfico da expressão no intervalo [0, 6] com 100 pontos.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
import math import matplotlib.pyplot as plt import numpy as np # Classes para nós da árvore class Node: def eval(self, x): raise NotImplementedError def infix(self): raise NotImplementedError class Const(Node): def __init__(self, value): self.value = value def eval(self, x): return self.value def infix(self): return str(self.value) class Var(Node): def eval(self, x): return x def infix(self): return 'x' class BinaryOp(Node): def __init__(self, left, right, op, symbol): self.left = left self.right = right self.op = op self.symbol = symbol def eval(self, x): return self.op(self.left.eval(x), self.right.eval(x)) def infix(self): return f"({self.left.infix()} {self.symbol} {self.right.infix()})" class UnaryOp(Node): def __init__(self, child, op, symbol): self.child = child self.op = op self.symbol = symbol def eval(self, x): return self.op(self.child.eval(x)) def infix(self): return f"{self.symbol}({self.child.infix()})" # Construção da árvore para (x + 1) * sin(x) - 2 # Primeiro montamos cada parte x_var = Var() um = Const(1) dois = Const(2) soma = BinaryOp(x_var, um, lambda a,b: a+b, '+') seno = UnaryOp(x_var, math.sin, 'sin') mult = BinaryOp(soma, seno, lambda a,b: a*b, '*') arvore = BinaryOp(mult, dois, lambda a,b: a-b, '-') # Avaliação para pontos específicos xs_teste = [0, 1, 2, 3, 4] ys_teste = [arvore.eval(x) for x in xs_teste] print("Avaliações:") for x, y in zip(xs_teste, ys_teste): print(f"f({x}) = {y:.4f}") # Expressão infixa print("\nExpressão infixa:", arvore.infix()) # Gráfico contínuo X = np.linspace(0, 6, 100) Y = [arvore.eval(x) for x in X] plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.plot(X, Y, 'b-', linewidth=2, label='(x+1)*sin(x)-2') plt.scatter(xs_teste, ys_teste, color='red', s=80, label='Pontos testados') plt.title('Árvore de Expressão: Avaliação Contínua') plt.xlabel('x') plt.ylabel('f(x)') plt.legend() plt.grid(True) plt.subplot(1, 2, 2) # Representação visual simplificada da árvore (texto) plt.text(0.1, 0.5, arvore.infix(), fontsize=14, family='monospace', bbox=dict(facecolor='lightyellow', alpha=0.8)) plt.axis('off') plt.title('Estrutura da Árvore (notação infixa)') plt.tight_layout() plt.show() |
Esse código cria a árvore manualmente e a avalia para valores de x. Ele também imprime a expressão com parênteses para mostrar a hierarquia. O primeiro gráfico exibe a curva contínua e os pontos discretos testados. O segundo gráfico mostra textualmente a estrutura da árvore. Para iniciantes, essa demonstração concretiza o conceito abstrato de árvore. A avaliação recursiva é clara e cada nó tem responsabilidade única. Além disso, a impressão infixa ajuda a verificar a correta precedência. Portanto, árvores de expressão são ferramentas poderosas e didáticas.