Generar un Árbol de Expresión

Submitted by juanjo23 on Mar, 01/03/2012 - 17:06

He creado una clase llamada ArbolExpresion que tiene la siguiente forma:

class ArbolExpresion{
        char type;              /* 'D' or 'P' */
        int value;                      /* for 'D' */
        ArbolExpresion left, rigth;     /* for 'P' */
        int operator;           /* for 'P' */
       
        public ArbolExpresion(char type, int value, ArbolExpresion left,
                        ArbolExpresion rigth, int operator) {
       
                this.type = type;
                this.value = value;
                this.left = left;
                this.rigth = rigth;
                this.operator = operator;
        }

        public ArbolExpresion(char type, int value, ArbolExpresion left, ArbolExpresion rigth) {
               
                this.type = type;
                this.value = value;
                this.left = left;
                this.rigth = rigth;
        }

        public ArbolExpresion(char type, ArbolExpresion left, ArbolExpresion rigth, int operator) {
                this.type = type;
                this.left = left;
                this.rigth = rigth;
                this.operator = operator;
        }      
}

y para ingresarle una expresion como: (2*((3*4)+9)) lo hago de la siguiente manera:

        ArbolExpresion ae = new ArbolExpresion('P', new ArbolExpresion ('D', 2, null, null), new ArbolExpresion('P', new ArbolExpresion('P', new ArbolExpresion('D', 3, null, null), new ArbolExpresion('D', 4, null, null), '*'), new ArbolExpresion('D', 9, null, null), '+'), '*' );

Asta aquí todo perfecto pero el problema que tengo es cuando quiero que la expresión que se ingrese al árbol sea una expresión que un usuario haya ingresado.
¿Alguien tiene idea de cómo puedo hacerlo?
Esta clase forma parte de un proyecto para un compilador que estoy haciendo.

‹ Problema básico con matrices en java Crear un jcheckbox y agregarlo a un panel al momento de activar otro jcheckbox ›

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.

Si, tienes que parsear la

Submitted by OscarRyz on Mar, 01/03/2012 - 23:15.

Si, tienes que parsear la entrada, convertila en tokens, aplicarle reglas y mientras se las aplicas generar estos árboles.

¬¬

Creo que no será de mucha ayuda lo que te escribí, pero así es.

Imagen de juanjo23

Gracias por responder, ya

Submitted by juanjo23 on Mié, 01/04/2012 - 00:17.

Gracias por responder, ya tengo los tokens, los cuales son obtenidos de la entrada del texto y después son enviados a un Analizador Léxico que verifica que los tokens pertenescan al lenguaje y después llamo al Analizador Sintactico que verifica que los tokens estén en orden correcto y esas cosas, pero no entiendo en que momento y como se pueden generar los árboles.
Me podrías ayudar un poco más o recomendarme algún enlace donde se explique como hacerlo.

El analizador sintáctico debe

Submitted by OscarRyz on Mié, 01/04/2012 - 05:09.

El analizador sintáctico debe de estar a esta altura recibiendo "algo", ese "algo", tiene ya información suficiente para caminar crear esta arbol.

Todo depende de como se vea ese algo, debe de ser otro árbol a esta altura. Lo que habrías de hacer es ver que información tiene ese algo y como está estructurado para "recorrerlo" y crear el arbol mientras lo recorres.

Como se ve el código del analizador sintáctico?

Saludos.

Imagen de juanjo23

En el Analizador Sináctico no

Submitted by juanjo23 on Mié, 01/04/2012 - 19:29.

En el Analizador Sináctico no recibo un árbol, recibo un conjunto de tokens que pertenecen a una sentencia y están dentro de un LinkedList lo que tengo en clase es un Grafo de estados con métodos como este tipo:

public void estadoInicio(){
                if(!tokens.isEmpty()){
                        switch(tokens.getFirst().getTipo()){                   
                                case IDENTIFICADOR: this.evaluarAsignacion(tokens);
                                        break;
                                case PALABRARESERVADA: this.sintaxisPalabraReservada(tokens);
                                        break;
                                        .
                                        .
                                        .
                                       
                                default: this.estadoErrores += "Error de sintaxis en la línea: "+tokens.getFirst().getLinea();        
                        }              
                }
        }

la clase token tiene está forma:

public class Token {
       
    private Tipo tipo;
    private String cadena;
    private int linea;

    constructores()...
    geters()...
    seters()...
   
}

¿Cómo podría hacerle para ir generando el Arbol de Expresion a partir de este conjunto de tokens?

Algoritmo Shunting-yard

Submitted by jpaul on Vie, 11/21/2014 - 11:53.

 

He aquí un procedimiento:

Teniendo la siguiente expresión: (2*((3*4)+9))

  1. Separa en tokens.

    (, 2, *, (, (, 3, *, 4, ), +, 9, ), )

  2. Convierte a notación posfija utilizando el algoritmo Shunting-yard (inventado por Edsger W. Dijkstra):

    2, 3, 4, *, 9, +, *

  3. Crea el árbol (mediante algún procedimiento recursivo), p.ej.:

    private Operation getOperation(List<String> list) {
        Collections.reverse(list);
        int size = list.size();
        if (size < 3) {
            throw new IllegalArgumentException("Illegal expression: " + list);
        }
        String operator = list.get(0);

        int indexA = 0;
        int indexB = 0;
        for (int i = 1;; i++) {
            String str = list.get(i);
            if (isOperator(str)) {
                indexA++;
            } else {
                indexB++;
            }
            if (indexA + 1 == indexB) {
                break;
            }
        }
        List<String> operandA = list.subList(1, 1 + indexA + indexB);
        List<String> operandB = list.subList(1 + indexA + indexB, size);
        if (operandA.size() == 1) {
            if (operandB.size() == 1) {
                return new Operation(operandB.get(0), operandA.get(0), operator);
            }
            return new Operation(getOperation(operandB), operandA.get(0), operator);
        }
        if (operandB.size() == 1) {
            return new Operation(operandB.get(0), getOperation(operandA), operator);
        }
        return new Operation(getOperation(operandB), getOperation(operandA), operator);
    }

  4. ¡Ya puedes hacer lo que quieras con el árbol!, p.ej.:

¡Por si sirve de algo!

~~~