Implementando uma pilha simples em Ruby

Há algumas semanas eu estava lendo um artigo sobre Máquinas de Minsky e o autor comentava sobre como implementar uma pilha (de inteiros) simples com alguns registradores. A idéia principal é usar o fato de que a multiplicação/divisão binária por 2^n desloca o valor do registrador exatamente n bits. Por exemplo, ao multiplicar um número por 4 (2^2), você está deslocando seus bits 2 “casas” na direção mais significativa (mais “alta”). Dividindo por 8 (2^3), os bits são deslocados na posição oposta 3 “casas”.

Partindo desse princípio, fica fácil implementar a pilha. Um registrador seria usado para armazenar a pilha e outro para a multiplicação/divisão. Para empilhar um número basta multiplicar o valor atual da pilha pela potência de dois correspondente ao número de bits que queremos armazenar e então somamos nosso valor.

Exemplo: Empilhar o valor 6 (1010)

Pilha atual (bit mais significativo à esquerda): 111001

Após multiplicação (por 2^4): 1110010000

Após soma: 1110011010

Para recuperar o topo da pilha, basta aplicar a operação “módulo” à pilha e à potência de 2 usada. Para retirar um valor, basta dividir pela mesma potência.

Código em ruby:

class SimpleStack
  def initialize(bits = 2)
    @stack = 0
    @size = 2**bits
  end
  def push(x)
    @stack *= @size
    @stack += x
  end
  def top
    @stack % @size
  end
  def pop
    result = top
    @stack /= @size
    result
  end
end

PS: De alguma forma o editor do wp.com não está indentando nem reconhecendo linhas em branco na tag “<code>”…


  1. Usa a tag que ele indenta certo.

    Como você fez pra mudar a cor do codigo? Eu tenho problemas quando posto código, pois fica muito parecido com o resto do texto.


Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s