Elf Blog

[UPDATE 20 Agosto 2010]

Nesses ultimo dias tinha criado uma classe para resolver as expressões na notação posfixa, segue o link do github:

http://github.com/edipofederle/PostfixEvaluation

Olá esse post irá ser um pouco diferente do que venho escrevendo por aqui, esse é um assunto assim digamos mais teórico(realmente a palavra não é essa), enfim, vou falar um pouco aqui sobre a notação Infixa e Posfixa, e também sobre o algoritmo para resolver uma conversão de infixa para posfixa.

Notação Infixa

Notaçao infixa é quando na expressão temos os operedatores binários colocados entre os operandos, ou seja o que estamos mais acostumados a fazer. Algo como:Sabemos que nessas expressões as vezes se faz necessário o uso de paranteses para nao ocorrer ambiguidade.(regras de prioridade). Por exemplo:NOTA #1: Estou considerando apenas oprações binárias.

Esse tipo de expressão torna o trabalho computacional muito mais complicado.

Notação Posfixa

Notação posfixa é aquela onde os operadores estão localizados após os operandos, dessa forma não se faz preciso parenteses. Por exemplo, a expressão acima ficaria assim:Simplificamos bem a expressão escrevendo ela de forma posfixa.

Convertendo Expressões de Infixa para Posfixa

Árvore de expressão Binária

Uma árvore de expressão binária nos mostra de forma clara a precedencias e a associetividade dos operadores em uma expressão, dada a expressão na notação infixa:temos a seguinte árvore de expressão:

Agora dada uma expressão na forma posfixa:temos a seguinte árvore de expressão:

Se avaliarmos essa expressão de forma “Postorder Traversal” iremos ter a expressão na forma posfixa.

Algoritmo

A conversão de infixa para Posfixa é feita usando uma técnica chamada operator precedence parsing, precisamos usar a estrutura de dados do tipo pilha(stack), o algoritmo funciona da seguinte forma.

Data um expressão infixa faça:

– Add um parenteses esquerdo ‘(‘ na pilha;
- Add um parenteses direito ‘)’ à expressão infixa;
- Enquanto a pilha não estiver vazia ler a expressão infixa da esquerda para a direita e então:
- se o caractere lido por um digito(ou variavel) -> então add na saida(posfixa);
- se o caractere lido por um parenteses esquerdo ‘(‘-> entao add na pilha;
- se o caractere for um operador entao faça:
- Enquanto operador no topo da pilha tiver precedencia igual ou maior que a do operador lido -> Remove operador do topo da pilha.
- add o caractere atual a pilha;
- se o caractere aqual for um parenteses direito ‘)’;
- enquanto não achar um parenteses esquerdo ‘(‘ no topo da pilha faça:
-> Remover operador do tipo da pilha e add a saida(posfixa)
-> remover e descartar o parenteses esquerdo ‘(‘;

Código Java

Baixo segue o link para o github onde esta a classe para em Java para conversão, vale lembrar que acabei por escrever esse post pois encontrei esse problema no site TDD Problems que por sinal recomendo a todos para práticar TDD e programação, tem problemas bem legais lá, desde coisas simples até complexas, entao de uma olhada no código que escrevi para esse problemas, não sei o quão bom esta, mas esta com todos testes de unidade passando , tentei deixar a classe bem limpa, clara e pequena, as funções estão pequenas, mas acho que não é o bastante ainda, podemos simplificar bem mais, alguns métodos estão um pouco feios também(necessita de mais refatoração certamente).

A classe é dividida nos seguintes métodos:

converterToPostFix(String infix)
removeFromStackUntilFindRightParenthesis(String postfix)
isADigit(String digit)
isOperator(String ch)
precedence(String top, String ex)

Acredito que os nomes estão bastante sugestivos quanto as suas responsabilidades.

Código Fonte: http://github.com/edipofederle/InfixToPostfixConverter

É isso pessoal, espero que tenha sido útil para alguem, e deixe-me saber de qualquer problema com esse código, podem criticar (mas fazm fork e arrumem a sujeira ).

Até Logo.

Este não será um post com texto, apenas uma implementaçao simples que fiz de uma pilha usando TDD + Junit com Java. Obviamente não usei a classe Stack do Java. Se alguem tiver sugestões so postar.

Primeiros os Testes de Unidade.

Depois as duas classes.

É isso, espero sugestoes e muitas criticas para refatorar

Antes de ler: http://en.wikipedia.org/wiki/Timestamp

Uma das coisas que eu sempre achei muito bacana no Rails é a parte do ActiveRecord,(active record pattern) uma característica que particularmente gosto é a criação automatica dos timestemp das tabelas no banco de dados, no Rails quando tempo um modelo(model) quase sempre temos um tabela relacionada a esse modelo no banco de dados, para título de curiosidade do pessoal do Java vou apresentar abaixo uma classe(model) que representa um produto.

OBS: essa linhda validates_presence_of: eu coloquei somente para não deixar a classe vazia, ela faz a validação do campo nome e descrição.

Simples não? Claro temos a migration para isso.

Ultimamente eu estou tendo um contado maior com Java e Hibernate, não vamos falar sobre Java vs Ruby aqui(ainda), então eu estava mapeando classes para o banco e me vi sem os timestamps, pensei, o hibernate é algo bacana provavelmente tenha algo parecido, uma olhada no google e na documentação e achei uma forma bem bacana e de certa forma elegante(não quanto o Ruby, xiita ) de se fazer tal funcionalidade.

Abaixo apresento uma classe Java Product que faz o uso do timestamp através de anotações do Hibernate.

Bom um tanto elegante também, mas … bom, tirei os gets e sets para deixar mais pequena, com essas anotações(@prePersist, @PreUpdate) iremos ter esses campos no banco igualmente temos no Rails, agora quando você persistir seu objeto ele ira gravar a data e a hora, e toda as vezes que você atualizar esse objeto no banco de dados ele irá atualizar a data e hora do campo updated, como na imagem a abaixo:

Bom pessoal esse post foi rápido e espero que tenha sido bom.

Até Logo.