O Blog mudou de endereço

Decidi adoptar um novo Blog engine baseado em java open source para poder parametrizar melhor. O novo site está em mleiria

Calculadora RPN

Uma expressão aritmética está em notação postfix (também chamada reverse polish notation ou RPN)se cada operador for colocado depois dos seus operandos. Por exemplo 3*(4+5) fica 3 4 5 + *. A notação 3*(4+5) chama-se infix. As expressões quando estão em notação postfix, são mais fáceis de serem processadas pelos computadores do que as expressões infix.
A seguinte classe processa expressões rpn e efectua as respectivas operações aritméticas. O centro nevrálgico do programa é o interface Deque e a classe ArrayDeque. Um deque é uma queue com duas saídas, ou seja, é uma estrutura linear que permite inserções e remoções só nos dois extremos (Deque).
Então, temos:

/**
 * Esta classe faz o parsing de expressões em postfix
 * (reverse polish notation)
 * e efectua as respectivas operações aritméticas
 *
 * @author Manuel
 *
 */
public class RPNCalculator {

	private static Deque stack =
		new ArrayDeque();
	/**
	 *
	 * @param input
	 */
	public static void calculate(String input) {
		char ch = input.charAt(0);
		if (ch == '+' || ch == '-' || ch == '*'
			|| ch == '/') {
			double y =
			  Double.parseDouble(
                                          stack.pop());
			double x =
			  Double.parseDouble(
			    stack.pop());
			double z = 0.0;
			switch (ch) {
			case '+':
				z = x + y;
				break;
			case '-':
				z = x - y;
				break;
			case '*':
				z = x * y;
				break;
			case '/':
				z = x / y;
				break;
			}
			System.out.printf
			  ("\t%.2f %c %.2f = %.2f%n",
			    x, ch, y, z);
			stack.push(new Double(z).toString());
		} else {
			stack.push(input);
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (true) {
			String input = in.nextLine();
			calculate(input);
			if(input.equalsIgnoreCase("q"))
				break;
		}
	}
}

A parte chata é que para fazer uma qualquer operação, temo primeiro que converter a expresão para a sua correspondente versão RPN. Segue um programa que faz isso mesmo:

public class ConvertInfixToPostfix {

	public static void main(String[] args){

		Deque stack =
			new ArrayDeque();
		String line =
			new Scanner(System.in).nextLine();
		System.out.println(line);
		Scanner scanner = new Scanner(line);
		while(scanner.hasNext()){
			if(scanner.hasNextInt()){
				System.out.print(
				  scanner.nextInt() + " ");
			}else{
				String str = scanner.next();
				if("+-*/".indexOf(str) >= 0){
					stack.push(str);
				}else if(str.equals(")")){
				  System.out.print(
				    stack.pop() + " ");
				}
			}
		}
		while(!stack.isEmpty()){
			System.out.print(stack.pop() + " ");
		}
		System.out.println();
	}
}

Dicas: pesquisa binária e pesquisa sequêncial

/**
 * Pesquisa um numero x num array ordenado.É
 * muito mais eficiente do que a pesquisa sequencial
 * mas requer que os elementos do array estejam ordenados.
 * Ele repetidamente divide a sequência em dois e em cada
 * vez restringe a pesquisa à metade que contém o elemento.
 *
 * Este algoritmo corre no tempo O(log(n)) o que quer dizer que
 * em média, o tempo de execução é proporcional ao logaritmo
 * do número de elementos no array.
 *
 *
 * @return o indice do numero x ou -1 se não encontrou
 */
public int binarySearch(int[] a, int x){

	int low = 0;
	int high = a.length;

	while(low < high){
		int i = (low + high) / 2;
		if(a[i] == x){
			return i;
		}else if(a[i] < x){
			low = i + 1;
		}else{
			high = i;
		}
	}
	return -1;
}
/**
 * Pesquisa sequencial (ou pesquisa linear) é o algoritmo
 * de pesquisa mais simples mas também é o menos eficiente.
 * Ele examina cada elemento sequencialmente começando
 * pelo primeiro elemento até chegar ao fim do array(se
 * eu estiver à procura de alguém num combóio, utilizo a
 * pesquisa sequencial)
 *
 * Este algoritmo corre no tempo O(n) o que quer dizer que
 * em média, o tempo de execução é proporcional ao número
 * de elementos no array.
 *
 * @return o indice do elemento a pesquisar ou 0 se não
 * o encontrar
 */
public int sequentialSearch(int[] a, int x){
	for(int i = 0, n = a.length; i < n; i++){
		if(a[i] == x){
			return i;
		}
	}
	return -1;
}
/**
 * O algoritmo de binarysearch pode encontrar elementos rapidamente
 * num array que já está ordenado o que sugere que devamos ter os
 * elementos ordenados no array.No entanto, inserir novos elementos
 * num array ordenado é difícil pois temos de transladar os elementos
 * maiores para arranjar espaço para o novo elemento.Podemos faze-lo
 * assim:
 * @param a o array
 * @param n o numero de elementos que já estão ordenados no array
 * @param x o elemento a ser inserido no meio dos elementos
 */
void insert(int[] a, int n, int x){
  /**PreCondicao: a[0] <= ... <= a[n-1], e n < a.length */
  /**PosCondicao: a[0] <= ... <= a[n], e x está entre eles */
  int i = 0;
  while(i < n && a[i] <= x){
  	i++;
  }
  System.arraycopy(a, i, a, i+1, n-i);
  a[i] = x;
}

Brincadeiras matemáticas 2

Este também é interessante:

Provar que qualquer número a é igual a um número menor b:
Sejam a, b, c quaisquer números tais que

a = b + c

então, multiplicando os dois lados por a – b, obtemos

a (a – b) = (b + c)(a – b)
a^2 -ab = ba – b^2 + ca – cb

passemos ac para o lado esquerdo,

a^2 – ab -ac = ab – b^2 – bc

factorizar,

a(a – b – c) = b(a – b – c)

dividindo ambos os lados por a – b – c obtemos

a = b

e esta?

Brincadeiras matemáticas

Eu tenho dois filhos e pelo menos um deles é rapaz.Qual é a probabilidade do outro ser rapaz?

Singleton: duas abordagens

Um Singleton é uma classe que só pode ser instanciada exactamente uma vez.
Temos duas abordagens possíveis. Em ambas mantemos o construtor privado e providenciamos membros to tipo public static de forma a que os clientes
possam aceder a uma e uma só instância da classe.

1. O membro public static é uma variável do tipo final:
   
//Singleton com uma variável final
public class A {
public static final A INSTANCE = new A();
private A() {}
}

   O construtor privado é chamado uma única vez para inicializar a variável A.INSTANCE que é do tipo public static final.
2. Providenciamos um método do tipo public static em vez da variável.
   
// Singleton with static factory
public class A {
private static final A INSTANCE = new A();
private A() {}
public static A getInstance() {
return INSTANCE;
}
}

   Todas as chamadas ao método estático a.getInstance()
   retornam uma referência ao mesmo objecto e não é possível criar mais nenhuma
   instância de A

A primeira abordagem deverá ser usada se tivermos a certeza absoluta que a classe
A será um Singleton para toda a vida enquanto que
a segunda abordagem dá-nos alguma flexibilidade no código, no sentido em que
agora a classe é do tipo Singleton mas mais tarde poderemos alterar esta
propriedade sem termos que alterar a API.

Uma nota sobre a serialização de Singletons:para tornarmos uma classe
singleton serializable, não é condição suficiente implementar o
interface Serializable á declaração da classe, i.e.,
public class A implements Serializable, temos de
implementar o método readResolve() caso contrário,
cada deserialização da instância irá resultar na criação de uma nova instância.
Para prevenir isto, deveremos adicionar o seguinte método à classe
A:

// metodo readResolve para preservar a propriedade singleton
private Object readResolve() throws ObjectStreamException {
/*
* Retorna a unica classe A e deixa o garbage colector
* tratar do resto
*/
return INSTANCE;
}


Redimensionar um array

Como redimensionar um array? Antes mais aconselho a darem uma vista de olhos pela
Collections framework e verem se há algo que satisfaça os requisitos (e.g. ArrayList
. Não há? Então vamos a isto:

public class Main {
/**
* @param args
*/
public static void main(String[] args) {

//Defino um array com 4 elementos
String[] names = new String[4];
names[0] = "ana";
names[1] = "ines";
names[2] = "carolina";
names[3] = "alice";

/**
* Mas agora por alguma razao recebo a informacao
* de que preciso mais um nome
* A solucao e realocar o array, criando uma estrutura dinamica
*/
String anotherName = "sofia";

//Criar um array temporario
String[] tmp = new String[names.length + 1];

//Copiar o array names para o array tmp
System.arraycopy(names, 0, tmp, 0, names.length);

//Copiar a referencia do array tmp para o array names
names = tmp; //o array tmp esta pronto para ser garbage collected

//A ultima casa do array names esta vazia.Adicionar a String
names[names.length-1] = anotherName;

//Vamos ver o resultado
for(String name: names)
System.out.println(name);
}
}

O resultado é o esperado:

ana
ines
carolina
alice
sofia


Nota final: esta técnica funciona bem para estruturas lineares simples mas para
estruturas mais complexas aconselho vivamente o uso de ArrayList
Em vez de System.arraycopy() poderia ter utilizado um ciclo
for mas System.arraycopy() é mais
rápido por ser implementado em código nativo.

Uso da memória pelos programas Java

As instruções de um programa a correr são temporariamente armazenados na memória do computador. Não é necessário o programador preocupar-se com a gestão da memória(coisa que não acontece em outras linguagens tais como o C ou C++): a JVM e o garbage collector tratam do assunto. Todavia ajuda sabermos onde são armazenados os dados na memória para termos uma melhor compreensão de como os objectos são criados. Consideremos a seguinte figura:

Há duas áreas distintas onde os dados de um programa são armazenados: stack e heap são duas formas (ou sítios) diferentes de armazenar em memória os elementos de um programa que está em execução.
Viver na Stack
Os seguintes elementos vivem na stack: Variáveis locais: as variáveis de tipos primitivos definidas dentro de um método ou como parâmetrosde um método.
Referências de variáveis locais:as variáveis que se referem a um objecto e são definidas dentro de um método ou como parâmetros de um método. Um objecto cuja variável local se refere vive na heap.
Invocações a métodos: quando invocamos um método, esse método é empurrado para a stack (i.e., é colocado no topo da stack
As variáveis locais vivem dentro do método e o seu alcance retringe-se ao método. Quando a execução do método termina, as variáveis locais desaparecem mas os objectos, cujas variáveis locais eventualmente se referem, continuam vivos na heap.
Viver na Heap
Os seguintes elementos vivem na heap:
Variáveis de instância: as variáveis de tipos primitivos definidas dentro da classe mas fora dos métodos.
Referências a variáveis de instância: as variáveis que se referem a um objecto e são definidas dentro da classe mas fora dos métodos.
Objectos: Todos os objectos vivem na heap

Resumindo: variáveis locais (primitivas ou referências) pertencem a métodos e vivem na stack enquanto que uma variável de instância pertence a um objecto e vive na heap. Todavia, uma referência de uma variável local na stack aponta para um objecto na heap e o objecto não morre com a morte da referência.
Os objectos que estão na heap que não estão a ser utilizados são, eventualmente, destruídos por um programa que se chama garbage collector de forma a libertar memória

Comparar Objectos com o Comparator

Tal como vimos no post anterior, ao implementarmos o interface Comparable, estamos a definir uma forma de comparar instâncias da classe
(no exemplo dado, o objectivo era criar uma lista de objectos Person ordenados por ordem de idades).
No entanto eu posso querer ter a flexibilidade de poder comparar objectos usando mais do que um critério (por exemplo, para uns
casos eu quero comparar idades mas noutros eu quero comparar os primeiros nomes). Resumindo, para criar objectos comparaveis
de duas formas diferentes, preciso de dois comparadores.

Procedimento:

criar um class que implementa o interface java.util.Comparator. Este interface tem um método:
compare com a seguinte assinatura:

	public int compare(Object o1, Object o2)

e retorna zero se o1 e o2 forem iguais, um inteiro negativo se o1
for menor do que o2 e um inteiro positivo se o1 for maior do que o2.

Tal como no método compareTo do interface Comparable, somos nós que decidimos qual
o critério que faz com que um objecto seja maior, igual ou menor do que o outro.

Continuando o exemplo do outro post, temos a class Person
que implementa o interface Comparable:

public class Person implements Comparable {
	private String firstName;

	private String lastName;

	private int age;

	public String getFirstName() {
		return firstName;
	}

	public String getLastName() {
		return lastName;
	}

	public int getAge() {
		return age;
	}

	public void setFirstName(String firstName) {
		this.firstName = firstName;
	}

	public void setLastName(String lastName) {
		this.lastName = lastName;
	}

	public void setAge(int age) {
		this.age = age;
	}

	public int compareTo(Object anotherPerson)
	throws ClassCastException {
	  if (!(anotherPerson instanceof Person))
	    throw new ClassCastException
               ("Objecto do tipo Person esperado!");
	    int anotherPersonAge = ((Person) anotherPerson).getAge();
	    return this.age - anotherPersonAge;
	  }
}

Até aqui nada de novo. Agora vou criar uma nova classe que implementa o interface Comparator
de forma a poder comparar objectos pelo último nome:

import java.util.Comparator;

public class LastNameComparator implements Comparator {

  public int compare(Object person, Object anotherPerson) {
    String lastName1 =
      ((Person)person).getLastName().toUpperCase();
    String lastName2 =
      ((Person)anotherPerson).getLastName().toUpperCase();
    return lastName1.compareTo(lastName2);

  }
}

e o mesmo para comparar o primeiro nome:

import java.util.Comparator;

public class FirstNameComparator implements Comparator {
  public int compare(Object person, Object anotherPerson) {
    String firstName1 =
      ((Person)person).getFirstName().toUpperCase();
    String firstName2 =
      ((Person)anotherPerson).getFirstName().toUpperCase();
  return firstName1.compareTo(firstName2);
  }
}

Vamos carregar um array com objectos do tipo
Person
e ordenar de diferentes formas:

public static void main(String[] args) {
	Person[] persons = new Person[3];
	persons[0] = new Person();
	persons[0].setFirstName("Marcus");
	persons[0].setLastName("Miller");
	persons[0].setAge(43);

	persons[1] = new Person();
	persons[1].setFirstName("Stanley");
	persons[1].setLastName("Clark");
	persons[1].setAge(35);

	persons[2] = new Person();
	persons[2].setFirstName("Jaco");
	persons[2].setLastName("Pastorious");
	persons[2].setAge(38);
	//Antes
	System.out.println("--Ordem natural");
	for(int i = 0; i  Ordenado por idade");
	for(int i = 0; i  Ordenado por primeiro nome");
	for(int i = 0; i  Ordenado por �ltimo nome");
	for(int i = 0; i < persons.length; i++){
		System.out.println(persons[i].getFirstName()
                   + ", " + persons[i].getLastName() + "," +
                persons[i].getAge());
	}
}

e o resultado é o esperado:

e o resultado é o esperado:
--Ordem natural
Marcus, Miller,43
Stanley, Clark,35
Jaco, Pastorious,38
--> Ordenado por idade
Stanley, Clark,35
Jaco, Pastorious,38
Marcus, Miller,43
--> Ordenado por primeiro nome
Jaco, Pastorious,38
Marcus, Miller,43
Stanley, Clark,35
--> Ordenado por �ltimo nome
Stanley, Clark,35
Marcus, Miller,43
Jaco, Pastorious,38
Se não quiser criar várias classes para os comparadores,

posso fazê-las inner classes da classe Person
public class Person implements Comparable{
	private String firstName;
	private String lastName;
	private int age;

	public String getFirstName() {
		return firstName;
	}
	public String getLastName() {
		return lastName;
	}
	public int getAge() {
		return age;
	}
	public void setFirstName(String firstName) {
		this.firstName = firstName;
	}
	public void setLastName(String lastName) {
		this.lastName = lastName;
	}
	public void setAge(int age) {
		this.age = age;
	}
	public int compareTo(Object anotherPerson)
                              throws ClassCastException{
	  if(!(anotherPerson instanceof Person))
	    throw new ClassCastException
                   ("Objecto do tipo Person esperado!");
	    int anotherPersonAge = ((Person)anotherPerson).getAge();
	    return this.age - anotherPersonAge;
	}

	public static Comparator LastNameComparator =
               new Comparator(){
  	public int compare(Object person, Object anotherPerson) {
	  String lastName1 =
                 ((Person)person).getLastName().toUpperCase();
	 String lastName2 =
                ((Person)anotherPerson).getLastName().toUpperCase();
  	return lastName1.compareTo(lastName2);
	 }
	}
	public static Comparator FirstNameComparator =
              new Comparator(){
  	public int compare(Object person, Object anotherPerson) {
	  String firstName1 =
                ((Person)person).getFirstName().toUpperCase();
	  String firstName2 =
                 ((Person)anotherPerson).getFirstName().toUpperCase();
  	return firstName1.compareTo(lastName2);
             }
          }
}
o que torna o código mais fácil de manter!

Comparar Objectos

Muitas vezes preciso de ir à base de dados e preencher listas (ou arrays) com objectos do tipo VO
(View Objects) para depois mostrar numa página web. Tenho necessidade de ordenar essa
lista baseado num critério qualquer. Supponhamos a seguinte situação: na base de dados
há uma tabela de pessoas com as colunas firstName, lastName, e age
e quero prencher uma lista com objectos do tipo Person:

public class Person {
	private String firstName;
	private String lastName;
	private int age;

	public String getFirstName() {
		return firstName;
	}
	public String getLastName() {
		return lastName;
	}
	public int getAge() {
		return age;
	}
	public void setFirstName(String firstName) {
		this.firstName = firstName;
	}
	public void setLastName(String lastName) {
		this.lastName = lastName;
	}
	public void setAge(int age) {
		this.age = age;
	}
}

Suponhamos agora que tenho um Array carregado com objectos do tipo Person
(com 3 objectos, por exemplo):

 /**
 * Hardcoded mas normalmente vem da base de dados sob a forma de resultset
 */
 		Person[] persons = new Person[3];
		persons[0] = new Person();
		persons[0].setFirstName("Marcus");
		persons[0].setLastName("Miller");
		persons[0].setAge(43);

		persons[1] = new Person();
		persons[1].setFirstName("Stanley");
		persons[1].setLastName("Clark");
		persons[1].setAge(35);

		persons[2] = new Person();
		persons[2].setFirstName("Jaco");
		persons[2].setLastName("Pastorious");
		persons[2].setAge(38);

Portanto, o que eu quero é ordenar este array por, digamos, primeiro nome ou idade.
Se utilizar o método sort da classe java.util.Arrays:

		 Arrays.sort(persons);

não funciona (envia uma excepção do tipo ClassCastException.
Naturalmente que posso escrever um algorítmo específico (tipo bubble sort) para ordenar
o array mas esta solução não é prática. A solução correcta passa por utilizar
o java.lang.Comparable interface. Implementando este interface,
torno as instâncias das classes comparáveis de acordo com critérios por mim definidos.

Vamos, então, implementar o interface Comparable. Este interface tem um
método, CompareTo, que determina como comparar duas instâncias
da classe. A sua assinatura é:

		 public int CompareTo(Object o)

que aceita como argumento um Object. Claro que só faz
sentido comparar instâncias do mesmo tipo. Podemos ver, também, que retorna um
inteiro que é igual a zero se o objecto passado é igual a esta instância e retorna
um inteiro positivo ou negativo se este objecto é maior ou menor do que o objecto
passado, respectivamente. Suponhamos que o critério de ordenação é a idade da pessoa:
A nossa classe Person fica assim:

public class Person implements Comparable{
	private String firstName;
	private String lastName;
	private int age;

	public String getFirstName() {
		return firstName;
	}
	public String getLastName() {
		return lastName;
	}
	public int getAge() {
		return age;
	}
	public void setFirstName(String firstName) {
		this.firstName = firstName;
	}
	public void setLastName(String lastName) {
		this.lastName = lastName;
	}
	public void setAge(int age) {
		this.age = age;
	}
	public int compareTo(Object anotherPerson) throws ClassCastException{
		if(!(anotherPerson instanceof Person))
			throw new ClassCastException("Objecto do tipo Person esperado!");
		int anotherPersonAge = ((Person)anotherPerson).getAge();
		return this.age - anotherPersonAge;
	}
}

Assim, se quiser ordenar o array por idades crescente, só tenho de fazer
Arrays.sort(Person).
Podemos testar:

public static void main(String[] args) {
		Person[] persons = new Person[3];
		persons[0] = new Person();
		persons[0].setFirstName("Marcus");
		persons[0].setLastName("Miller");
		persons[0].setAge(43);

		persons[1] = new Person();
		persons[1].setFirstName("Stanley");
		persons[1].setLastName("Clark");
		persons[1].setAge(35);

		persons[2] = new Person();
		persons[2].setFirstName("Jaco");
		persons[2].setLastName("Pastorious");
		persons[2].setAge(38);
		System.out.println("ORDEM NATURAL:");
		for(int i = 0; i < persons.length; i++){
			System.out.println(persons[i].getFirstName() + ", " +
                        persons[i].getLastName() + "," + persons[i].getAge());
		}
		Arrays.sort(persons);
		System.out.println("ORDENADO POR IDADE");
		for(int i = 0; i < persons.length; i++){
			System.out.println(persons[i].getFirstName() + ", " +
                        persons[i].getLastName() + "," + persons[i].getAge());
		}
}

e o output é o esperado:

ORDEM NATURAL:
Marcus, Miller,43
Stanley, Clark,35
Jaco, Pastorious,38
ORDENADO POR IDADE
Stanley, Clark,35
Jaco, Pastorious,38
Marcus, Miller,43

Se quiser ordenar, não por idade mas por, digamos, primeiro nome, só tenho de
adaptar o meu método CompareTo:

	public int compareTo(Object anotherPerson) throws ClassCastException{
		if(!(anotherPerson instanceof Person))
			throw new ClassCastException("Objecto do tipo Person esperado!");
		String anotherPersonFirstName = ((Person)anotherPerson).getFirstName();
		return this.firstName.compareTo(anotherPersonFirstName);
	}

E se eu quiser ter alguma flexibilidade no código para ordenar ou por idade, ou
por primeiro nome ou por último nome, conforme a situação? isso será matéria
para o próximo post (iremos implementar o interface java.util.Comparator