Quero análisar uma séria de tokens em Java implementando o Shunting-yard algorithm. Qual a melhor forma de diferenciar um token do outro, usando o operador instanceof, usando enum ou outra solução?

Programação Java
#1

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 ifs, 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?

#2

Se você tiver que usar estruturas condicionais, como if ou switch-case então é melhor utilizar enumerações ao invés de instanceof.

1 curtida
#3

Use polimorfismo da orientação a objetos. Ex:

public abstract class Animal {
      protected abstract String say();

   //outros métodos
}

public class Dog extends Animal {
   String say() {
        System.out.println("Au au");
   }
}

public class Cat extends Animal {
   String say() {
        System.out.println("Miau");
   }
}

public class App {
   public static void main(String args[]) {
       Animal dog = new Dog();
       dog.say();

       Animal cat = new Cat();
       cat.say();
  }
}

O say vai fazer dependendo da instancia que vier, voce pode fazer o mesmo pro push do Token. (Pode ter erro de sintaxe no meu código, pois programei diretamente aqui no editor do forum)

1 curtida
#4

@rmendes08 é mesmo e por algum motivo me parece mais certo usar enums. Quando penso em usar o instanceof minha alma sente que alguma coisa tá errada.

@igor_ks de acordo com o algoritmo que quero implementar eu não poderia tratar números e operadores indiscriminadamente. Eu realmente tenho que diferenciá-los em algum momento para saber para qual pilha aquele token vai.

De qualquer forma tô aqui pensando ainda em como fazer isso da melhor maneira possivel. Qualquer idéia não exitem em compartilhar. Valeu pelas respostas!