Quero criar um programa que converte expressões matemáticas especificadas em infix notation (Ex.: 1 + 2) para postfix notation (Ex.: 1 2 +) usando o Shunting-yard algorithm em Java.
Este algoritmo considera a existência de números, operadores (com diferentes níveis de precedência e associabilidade), funções e parenteses. Mas, para simplificar, vamos considerar apenas a existência de números e dos operadores de soma e subtração.
Fazer a conversão é relativamente simples, minha dúvida é como implementar a diferenciação entre um token de outro. Ou seja, qual a melhor forma de dizer se um token representa um número ou um operador.
Até agora tenho duas idéias, usar o instanceof ou usar enums.
Na primeira idéia eu tenho as classes Token
, Number
e Operator
.
class Token {}
class Number extends Token {
final int value;
Number(int value) { this.value = value; }
public String toString() { return String.valueOf(value); }
}
class Operator extends Token {
final char operation;
Operator(char operation) { this.operation = operation; }
public String toString() { return String.valueOf(operation); }
}
E o código que análisa a expressão seria algo como isso:
import java.util.Stack;
public class InfixToPostfixConverter {
static Stack<Token> output = new Stack<>();
static Stack<Token> ops = new Stack<>();
static void parse(Stack<Token> tokens) {
while ( !tokens.isEmpty() ) {
Token token = tokens.pop();
if ( token instanceof Number )
output.push( token );
else if ( token instanceof Operator ) {
while ( !ops.isEmpty() )
output.push( ops.pop() );
ops.push( token );
}
}
// Esvaziando a pilha de operadores
while ( !ops.isEmpty() )
output.push( ops.pop() );
}
public static void main(String[] args) {
Stack<Token> tokens = new Stack<>();
// Aqui eu componho a expressão apenas para testes
tokens.push( new Number(789) );
tokens.push( new Operator('+') );
tokens.push( new Number(456) );
tokens.push( new Operator('-') );
tokens.push( new Number(123) );
parse( tokens );
// Imprimindo o resultado da conversão
System.out.print(output);
}
}
Como você pode ver eu uso instanceof para dizer se o Token é número ou operador, no exemplo isso requer apenas dois if
s, mas para implementar o algoritmo completo eu precisaria de, pelo menos, mais 4 o que deixaria o código meio estranho na minha opinião.
Então eu tenho uma outra idéia que seria usar um enum. Minhas classes ficariam mais ou menos assim:
class Token {
enum Kind { NUMBER, OPERATOR }
final Kind KIND;
Token(Kind kind) { this.KIND = kind; }
}
class Number extends Token {
final int value;
Number(int value) {
super(Kind.NUMBER);
this.value = value;
}
public String toString() { return String.valueOf(value); }
}
class Operator extends Token {
final char operation;
Operator(char operation) {
super(Kind.OPERATOR);
this.operation = operation;
}
public String toString() { return String.valueOf(operation); }
}
E no código para fazer a análise eu teria que mudar o método parse
que ficaria assim:
static void parse(Stack<Token> tokens) {
while ( !tokens.isEmpty() ) {
Token token = tokens.pop();
switch ( token.KIND ) {
case NUMBER:
output.push( token );
break;
case OPERATOR:
while ( !ops.isEmpty() )
output.push( ops.pop() );
ops.push( token );
break;
}
}
while ( !ops.isEmpty() )
output.push( ops.pop() );
}
Qual seria a solução mais elegante, a primeira ou segunda idéia? Você tem alguma dica ou sugestão? Existe forma melhor de implementar o que quero?