Skip to content

Instantly share code, notes, and snippets.

@lrlucena
Last active June 16, 2022 22:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lrlucena/e7690498af4d0ecec1c987bfb9022371 to your computer and use it in GitHub Desktop.
Save lrlucena/e7690498af4d0ecec1c987bfb9022371 to your computer and use it in GitHub Desktop.
Árvore

Árvore Binária de Expressão

Código Fonte

Construção de uma árvore binária para representar expressões aritmética envolvendo números inteiros e os operadores binários +, -, *, /.

O programa lê uma expressão aritmética escrita em notação polonesa e gera uma árvore binária para representá-la. Depois cálcula o valor da expressão e reescreve a expressão na notação prefixa e infixa.

Entrada

1 2 3 * +

Árvore

flowchart TB
  + --> 1
  + --> *
  * --> 2
  * --> 3

Saída

Soma(Valor(1),Multiplicação(Valor(2),Valor(3)))
Infixo : (1 + (2 * 3))
Prefixo: + 1 * 2 3
Posfixo: 1 2 3 * +
Eval   : 7

Implemenação

Usamos tipos (classes) para representar os nós da árvores binária.

classDiagram
    class Nó {
      << abstrato >>
      ~eval() Inteiro
      ~tamanho() Inteiro
      ~prefixo() Texto
      ~infixo() Texto
      ~posfixo() Texto
    }
    
    class Operaçao {
      << abstrato >>
      ~simbolo() Texto
      tamanho() Inteiro
      prefixo() Texto
      infixo() Texto
      posfixo() Texto
    }
    
    Nó <-- Operaçao : esquerda
    Nó <|.. Operaçao
    Nó <-- Operaçao : direita
        
    Nó <|.. Valor
    
    class Soma {
      símbolo = "+"
      Soma(Nó, Nó)
      eval() Inteiro
    }
    
    class Subtraçao {
      símbolo = "-"
      Subtraçao(Nó, Nó)
      eval() Inteiro
    }
    
    class Multiplicaçao {
      símbolo = "*"
      Multiplicaçao(Nó, Nó)
      eval() Inteiro
    }

    class Divisao {
      símbolo = "/"
      Divisao(Nó, Nó)
      eval() Inteiro
    }
    
    Operaçao <|.. Soma
    Operaçao <|.. Subtraçao
    Operaçao <|.. Multiplicaçao
    Operaçao <|.. Divisao
    
    class Valor {
      Inteiro tamanho = 1
      Valor(Inteiro)
      prefixo() Texto
      infixo() Texto
      posfixo() Texto
    }

tipo abstrato 
  eval(): Inteiro
  tamanho(): Inteiro
  prefixo(): Texto
  infixo(): Texto
  posfixo(): Texto
fim

tipo abstrato Operação: 
  esquerda(): 
  direita() : 
  símbolo() : Texto
  tamanho() = 1 + esquerda.tamanho + direita.tamanho
  prefixo() = "{símbolo} {esquerda.prefixo} {direita.prefixo}"
  infixo()  = "({esquerda.infixo} {símbolo} {direita.infixo})"
  posfixo() = "{esquerda.posfixo} {direita.posfixo} {símbolo}"
fim

tipo Valor: 
  eval: Inteiro
  tamanho = 1
  prefixo, infixo, posfixo = eval.texto
fim

tipo Soma: Operação
  esquerda, direita: 
  símbolo = "+"
  eval() = esquerda.eval + direita.eval
fim

tipo Subtração: Operação
  esquerda, direita: 
  símbolo = "-"
  eval() = esquerda.eval - direita.eval
fim

tipo Multiplicação: Operação
  esquerda, direita: 
  símbolo = "*"
  eval() = esquerda.eval * direita.eval
fim

tipo Divisão: Operação
  esquerda, direita: 
  símbolo = "/"
  eval() = esquerda.eval div direita.eval
fim

A função recursiva árvore recebe uma pilha de tokens (números e símbolos) de uma expressão arimética em notação reversa e gera uma árvore binária cujos nós são os elementos da expressão.

arvore(pilha: Lista[Texto]):  =
  se ["+", "-", "*", "/"].contem(pilha.cabeça) então
    operação = escolha pilha.cabeça
      caso "+" => Soma
      caso "-" => Subtração
      caso "*" => Multiplicação
      caso "/" => Divisão
    fim
    direita  = arvore(pilha.cauda)
    esquerda = arvore(pilha.cauda.descarte(direita.tamanho))
    operação(esquerda, direita)
  senão
    Valor(pilha.cabeça.inteiro)
  fim

pilha = leia_texto.divida(" ").inverta
a = arvore(pilha)
escreva a
escreva "Infixo : {a.infixo}"
escreva "Prefixo: {a.prefixo}"
escreva "Posfixo: {a.posfixo}"
escreva "Eval   : {a.eval}"
tipo abstrato Nó
eval(): Inteiro
tamanho(): Inteiro
prefixo(): Texto
infixo(): Texto
posfixo(): Texto
fim
tipo abstrato Operação: Nó
esquerda(): Nó
direita() : Nó
símbolo() : Texto
tamanho() = 1 + esquerda.tamanho + direita.tamanho
prefixo() = "{símbolo} {esquerda.prefixo} {direita.prefixo}"
infixo() = "({esquerda.infixo} {símbolo} {direita.infixo})"
posfixo() = "{esquerda.posfixo} {direita.posfixo} {símbolo}"
fim
tipo Valor: Nó
eval: Inteiro
tamanho = 1
prefixo, infixo, posfixo = eval.texto
fim
tipo Soma: Operação
esquerda, direita: Nó
símbolo = "+"
eval() = esquerda.eval + direita.eval
fim
tipo Subtração: Operação
esquerda, direita: Nó
símbolo = "-"
eval() = esquerda.eval - direita.eval
fim
tipo Multiplicação: Operação
esquerda, direita: Nó
símbolo = "*"
eval() = esquerda.eval * direita.eval
fim
tipo Divisão: Operação
esquerda, direita: Nó
símbolo = "/"
eval() = esquerda.eval div direita.eval
fim
arvore(pilha: Lista[Texto]): Nó =
se ["+", "-", "*", "/"].contem(pilha.cabeça) então
operação = escolha pilha.cabeça
caso "+" => Soma
caso "-" => Subtração
caso "*" => Multiplicação
caso "/" => Divisão
fim
direita = arvore(pilha.cauda)
esquerda = arvore(pilha.cauda.descarte(direita.tamanho))
operação(esquerda, direita)
senão
Valor(pilha.cabeça.inteiro)
fim
pilha = leia_texto.divida(" ").inverta
a = arvore(pilha)
escreva a
escreva "Infixo : {a.infixo}"
escreva "Prefixo: {a.prefixo}"
escreva "Posfixo: {a.posfixo}"
escreva "Eval : {a.eval}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment