Mão na massa: Interpreter

Problema:

Reconhecer padrões é um problema bem complicado, no entanto, quando conseguimos formular uma gramática para o problema a solução fica bem mais fácil. Suponha que é preciso converter uma String representando um número romano em um inteiro que represente seu valor decimal. É fácil perceber que este problema trata-se de reconhecer determinados padrões.

Percorrer a String e procurar cada um dos possíveis casos não é a melhor solução, pois dificultaria bastante a manutenção do código. Então vamos tentar formular o problema como uma gramática. Para simplificar, vamos tratar apenas números de quatro dígitos.

Iniciando a definição da gramática, um número romano é composto por caracteres que representam números de quatro, três, dois ou um dígito:

numero romano ::= {quatro dígitos} {três dígitos} {dois dígitos} {um dígito}

Números de quatro, três, dois e um dígito são formados por caracteres que representam nove, cinco, quatro e um. Com estes caracteres é possível representar qualquer um dos número em romanos:

quatro dígitos ::= um
três dígitos ::= nove | cinco {um} {um} {um} | quatro | um
dois dígitos ::= nove | cinco {um} {um} {um} | quatro | um
um dígito ::= nove | cinco {um} {um} {um} | quatro | um

O “cinco” em romano pode vir seguido por até três números “um”.

E finalmente, os caracteres que representam nove, cinco, quatro e um são os seguinte, considerando apenas números de quatro dígitos:

nove ::= “CM”, “XC”, “IX”
cinco ::= “D”, “L”, “V”
quatro ::= “CD”, “XL”, “IV”
um ::= “M”, “C”, “X”, “I”

Com estas regras podemos criar vários números romanos, por exemplo, CI é igual a 101, pelas regras definidas a construção seria:

número romano -> {três digitos} {um dígito} -> {um} {um dígito} -> C {um dígito} -> C {um} -> CI

Outro exemplo, CXCIV é 194, pelas regras seria:

número romano -> {três digitos} {dois dígitos} {um dígito} -> {um} {dois dígitos} {um dígito} -> C {dois dígitos} {um dígito} -> C {nove} {um dígito} -> C XC {um dígito} -> C XC {quatro} -> CXCIV

Uma vez definida a grámatica e suas regras, é possível utilizar o padrão Interpreter para montar uma estrtura para interpretar os comandos.

Interpreter

Vejamos a intenção do padrão:

“Dada uma linguagem, definir uma representação para sua gramática juntamente com um interpretador que usa a representação para interpretar sentenças dessa linguagem.” [1]

Ou seja, dada a linguagem, números romanos, construir uma representação para a gramática dela junto com um interpretador para essa gramática.

A estrutura do padrão é muito parecido com a do padrão Composite , é definido inicialmente uma classe abstrata que será a base de todas as classes interpretadoras. Nela é construída a interface básica e o método de interpretar. Este método recebe como atributo um contexto, que é uma classe que vai armazenar as informações de entrada e saída.

Vamos então definir a classe contexto para o nosso problema:

public class Contexto {
	protected String input;
	protected int output;

	public Contexto(String input) {
		this.input = input;
	}

	public String getInput() {
		return input;
	}

	public void setInput(String input) {
		this.input = input;
	}

	public int getOutput() {
		return output;
	}

	public void setOutput(int output) {
		this.output = output;
	}
}

Não se preocupe com os getters e setters, eles serão necessários quando formos definir o método de interpretação. O que merece a atenção nesta classe são os atributos de input, que é a String em formato romano, e o output, que é o inteiro que vai armazenar o valor.

Vamos analisar a classe interpretadora em partes. Primeiro vamos dar uma olhada no método de interpretação:

public abstract class NumeroRomanoInterpreter {
	public void interpretar(Contexto contexto) {
		if (contexto.getInput().length() == 0) {
			return;
		}
		// Os valores nove e quatro são os únicos que possuem duas casas
		// Ex: IV, IX
		if (contexto.getInput().startsWith(nove())) {
			adicionarValorOutput(contexto, 9);
			consumirDuasCasasDoInput(contexto);
		} else if (contexto.getInput().startsWith(quatro())) {
			adicionarValorOutput(contexto, 4);
			consumirDuasCasasDoInput(contexto);
		} else if (contexto.getInput().startsWith(cinco())) {
			adicionarValorOutput(contexto, 5);
			consumirUmaCasaInput(contexto);
		}
		// Os valores de um são os únicos que repetem, ex: III, CCC, MMM
		while (contexto.getInput().startsWith(um())) {
			adicionarValorOutput(contexto, 1);
			consumirUmaCasaInput(contexto);
		}
	}

	private void consumirUmaCasaInput(Contexto contexto) {
		contexto.setInput(contexto.getInput().substring(1));
	}

	private void consumirDuasCasasDoInput(Contexto contexto) {
		contexto.setInput(contexto.getInput().substring(2));
	}
}

Este método recebe o contexto e a ideia é fazer o seguinte: comparar os primeiros caracteres da String com os caracteres que representam nove, quatro, cinco e um. Quando um destes padrões for encontrado é retirado da String, para que não seja repetido, e o seu valor é adicionado ao valor de output do contexto.

Um detalhe que deve ser observado é que os valores que representam nove ou quatro possuem dois caracteres, assim é necessário retirar dois caracteres da string de input. Feito o método de interpretação é necessário definir as strings que vão representar os caracteres nove, cinco, quatro e um.

Além disso, existe outro método não definido, o “multiplicador()”. Este método vai retornar qual o valor relativo do número, por exemplo, se for um número romano de quatro dígitos, o método retornará 1000, se for um de três retornará 100, etc.

public abstract class NumeroRomanoInterpreter {

	...

	public abstract String um();

	public abstract String quatro();

	public abstract String cinco();

	public abstract String nove();

	public abstract int multiplicador();
}

Estes métodos serão definidos nas subclasses. Lembra das definições das regras da gramática? Cada regra daquela vai se tornar uma classe derivada da classe interpretadora. Nela vão ser definidas as strings de um, quatro, cinco e nove. Também será definido o multiplicado relativo de cada uma.

Vejamos então como exemplo a definição da classe que representa números de um dígito:

public class UmDigitoRomano extends NumeroRomanoInterpreter {

	@Override
	public String um() {
		return "I";
	}

	@Override
	public String quatro() {
		return "IV";
	}

	@Override
	public String cinco() {
		return "V";
	}

	@Override
	public String nove() {
		return "IX";
	}

	@Override
	public int multiplicador() {
		return 1;
	}

}

Nesta classe definimos os números de um dígito, ou uma casa decimal, em caracteres romanos: I, IV, V e IX. O valor do multiplicador será 1. Como outro exemplo, vejamos a classe que representam números de dois dígitos:

public class DoisDigitosRomano extends NumeroRomanoInterpreter {

	@Override
	public String um() {
		return "X";
	}

	@Override
	public String quatro() {
		return "XL";
	}

	@Override
	public String cinco() {
		return "L";
	}

	@Override
	public String nove() {
		return "XC";
	}

	@Override
	public int multiplicador() {
		return 10;
	}

}

De maneira análoga, nesta classe são definidos os número de duas casas decimais: X, XL, L e XC. O valor do multiplicador será 10. As outras classes seguirão da mesma maneira.

Então vejamos como ficaria o cliente do interpreter deste exemplo:

	public static void main(String[] args) {
		ArrayList interpretadores = new ArrayList();
		interpretadores.add(new QuatroDigitosRomano());
		interpretadores.add(new TresDigitosRomano());
		interpretadores.add(new DoisDigitosRomano());
		interpretadores.add(new UmDigitoRomano());

		String numeroRomano = "CXCIV";
		Contexto contexto = new Contexto(numeroRomano);

		for (NumeroRomanoInterpreter numeroRomanoInterpreter : interpretadores) {
			numeroRomanoInterpreter.interpretar(contexto);
		}

		System.out.println(numeroRomano + " = "
				+ Integer.toString(contexto.getOutput()));
	}

Primeiro criamos uma lista onde vamos inserir todos os interpretadores, depois, vamos iterar sobre essa lista chamando os métodos de interpretação e passando um mesmo contexto como parâmetro. No final, podemos verificar o resultado pela saída no terminal.

O exemplo completo pode ser baixado pelo repositório do GitHub, link no final do post. Experimente executar outras instâncias de números romanos e observar o fluxo de chamadas para entender melhor como o padrão foi aplicado.

O diagrama UML para este caso é o seguinte:

Um pouco de teoria

Pelo exemplo vimos que a maior dificuldade em utilizar o Interpreter é na verdade conseguir modelar uma gramática para o problema. Feito isso, cada regra da gramática acaba se tornando uma subclasse da expressão abstrata. Desta maneira é fácil implementar a gramática, as classes interpretadoras ficam bem simples.

Outro ponto é a facilidade de alteração e extensão da gramática, pois basta criar novas classes que implementem as novas regras. Suponha que agora a gramática precisa abranger números de cinco dígitos? Basta criar uma nova classe que defina essas regras e alterar o método de interpretação.

Este método de interpretação, quando observado de perto, lembra bastante outro padrão, o Template Method. Perceba que ele define um algoritmo padrão de interpretação e deixa alguns pontos ganchos que deverão ser implementados nas subclasses.

O padrão Interpreter se assemelha bastante ao Composite. Ambos podem ser entendidos com a ideia de árvores, já que existe uma classe terminal ou folha, e uma classe composta ou nó. Basta analisar os diagramas UML dos dois padrões para perceber a semelhança.

No exemplo citado não houve a necessidade de utilizar uma classe interpreter que tivesse outros objetos interpreter. No entanto pense no seguinte exemplo: a notação musical é composta de notas, que seriam os terminais, e acordes, que seriam agrupamentos de notas. Então um método de interpretação em notas poderia tocar a nota e um método de interpretação em acorde tocaria cada uma das notas do acorde.

A diferença entre os dois padrões é que o Composite, obrigatoriamente define métodos para gerenciamento da estrutura. Na classe composta são encontrados os métodos de adição e remoção de elementos. Já no Interpreter, esses métodos não são necessários, a ideia de árvore é utilizada apenas para facilitar a visualização.

Outra grande diferença é que o padrão Interpreter depende de um contexto externo, enquanto que no Composite esse contexto é desnecessário. No entanto, ambos os padrão se utilizam, pois, geralmente um Composite define alguma operação de interpretação, e a estrutura do Interpret geralmente é um Composite.

Código fonte completo

O código completo pode ser baixado no seguinte repositório Git: https://github.com/MarcosX/Padr-es-de-Projeto.

Os arquivos estão como um projeto do eclipse, então basta colocar no seu Workspace e fazer o import.

Se gostou do post compartilhe com seus amigos e colegas, senão, comente o que pode ser melhorado. Encontrou algum erro no código? Comente também. Possui alguma outra opinião ou alguma informação adicional? Comenta ai! 😀

Referências:

[1] GAMMA, Erich et al. Padrões de Projeto: Soluções reutilizáveis de software orientado a objetos.

Anúncios