Analizando una expresión aritmética y construyendo un árbol en Java

Question

Necesité ayuda para crear árboles personalizados con una expresión aritmética. Digamos, por ejemplo, introducir esta expresión aritmética:

(5+2)*7 

El árbol de resultados debe ser similar:

* 
/\ 
    + 7 
/\ 
5 2 

tengo algunas clases personalizadas para representar los diferentes tipos de nodos, es decir PlusOp, LeafInt, etc. No necesito evaluar la expresión, simplemente creo el árbol, entonces puedo realizar otras funciones más tarde. Además, el operador negativo '-' solo puede tener un hijo, y para representar '5-2', debe ingresarlo como 5 + (-2).

Se requerirá alguna validación sobre la expresión para asegurar que cada tipo de operador tenga el no correcto. de argumentos/niños, cada corchete de apertura va acompañado de un corchete de cierre.

Además, probablemente debería mencionar que mi amigo ya ha escrito un código que convierte la cadena de entrada en una pila de tokens, si eso va a ser útil para esto.

Agradecería cualquier ayuda. Gracias :)

(He leído que puedes escribir una gramática y usar antlr/JavaCC, etc. para crear el árbol de análisis sintáctico, pero no estoy familiarizado con estas herramientas o con la escritura de gramáticas, así que si esa es tu solución, Le agradecería si pudiera proporcionar algunos útiles tutoriales/enlaces para ellos.)

Answer 1

El "Five minute introduction to ANTLR" incluye un ejemplo de gramática aritmética. Vale la pena echarle un vistazo, especialmente porque antlr es de código abierto (licencia BSD).

Answer 2

Varias opciones para usted:

1. volver a utilizar un analizador de expresión existente. Eso funcionaría si eres flexible en sintaxis y semántica. Una buena que recomiendo es el lenguaje de expresiones unificadas integrado en Java (inicialmente para uso en archivos JSP y JSF).

2. Escriba su propio analizador desde cero. Existe una forma bien definida de escribir un analizador que tenga en cuenta la precedencia del operador, etc. Describir exactamente cómo se hace eso queda fuera del alcance de esta respuesta. Si sigue esta ruta, encuentre un buen libro sobre diseño de compiladores. La teoría del análisis de lenguaje se tratará en los primeros capítulos. Normalmente, el análisis de expresiones es uno de los ejemplos.

3. Use JavaCC o ANTLR para generar lexer y analizador. Prefiero JavaCC, pero cada uno es suyo. Simplemente googlee "muestras de javacc" o "muestras de antlr". Encontrarás mucho.

Entre 2 y 3, recomiendo 3 incluso si tiene que aprender nuevas tecnologías. Hay una razón por la que se han creado generadores de analizadores sintácticos.

También tenga en cuenta que la creación de un analizador que puede manejar entradas incorrectas (no solo falla con la excepción de parse) es mucho más complicado que escribir un analizador que solo acepta entradas válidas. Básicamente, debes escribir una gramática que describa los diversos errores de sintaxis comunes.

Actualización: Este es un ejemplo de un analizador de lenguaje de expresiones que escribí usando JavaCC. La sintaxis está basada libremente en el lenguaje de expresión unificado.Debería darte una buena idea de a qué te enfrentas.

Contents of org.eclipse.sapphire/plugins/org.eclipse.sapphire.modeling/src/org/eclipse/sapphire/modeling/el/parser/internal/ExpressionLanguageParser.jj

Answer 3

Asumiendo que esto es algún tipo de tarea y desea hacerlo usted mismo ..

Lo hice una vez, necesita una pila

Entonces, ¿qué haces para el ejemplo es :

 
    parse what to do?    Stack looks like 
     (  push it onto the stack  (
     5  push 5      (, 5 
     +  push +      (, 5, + 
     2  push 2      (, 5, +, 2 
    )  evaluate until (   7    
     *  push *      7, * 
     7  push 7      +7, *, 7 
     eof evaluate until top   49 

los símbolos como "5" o "+" solo se pueden almacenar como cadenas u objetos simples, o se puede almacenar el + como un objeto +() sin juego los valores y los establece cuando está evaluando.

Supongo que esto también requiere un orden de precedencia, así que describiré cómo funciona.

en el caso de: 5 + 2 * 7

usted tiene que empujar empuje 5 + 2 siguiente empujar op es mayor precedencia de modo que lo empuje, así, a continuación, empuje los tres. Cuando encuentre ya sea a) o el final del archivo o un operador con precedencia inferior o igual, comenzará a calcular la pila al anterior (o al comienzo del archivo.

Porque su pila ahora contiene 5 + 2 * 7, cuando lo evalúas, sacas el 2 * 7 primero e insertas el * (2,7) nodo resultante en la pila, luego, una vez más, evalúas los tres elementos superiores en la pila (5 + * nodo) para que el árbol salga correctamente

Si se ordenó de la otra manera: 5 * 2 + 7, presionarías hasta llegar a una pila con "5 * 2" y luego tocarías la precedencia más baja + lo que significa que evaluarás lo que tienes ahora. Evaluarías el 5 * 2 en un nodo * y lo presionarás, luego continuarías presionando + y 3 para tener * nodo + 7, en ese punto evaluarías eso.

Esto significa que tiene una "precedencia de la corriente más alta" que almacena un 1 cuando presiona un +/-, un 2 cuando presiona un * o/y un 3 para "^". De esta forma, puede probar la variable para ver si la precedencia de su próximo operador es < = su precedencia actual.

si ")" se considera prioritaria 4 se puede tratar como otros operadores, excepto que elimina el juego "(", una prioridad más baja no lo haría.

Answer 4

quería responder a la respuesta de Bill K. , pero no tengo la reputación de agregar un comentario allí (en realidad es donde pertenece esta respuesta). Puedes pensar en esto como una adición a la respuesta de Bill K., porque la suya era un poco incompleta. La consideración que falta es operator associativity; , cómo analizar expresiones como:

49/7/7 

Dependiendo de si la división es asociativa izquierda o derecha, la respuesta es:

49/(7/7) => 49/1 => 49 

o

(49/7)/7 => 7/7 => 1 

Típicamente, se consideran división y la resta para ser dejado asociativa (es decir, caso dos, arriba), mientras que la exponenciación es asociativa derecha. Por lo tanto, cuando se encuentra con una serie de operadores con la misma precedencia, quiere analizarlos en orden si se dejan asociativos o en orden inverso si son asociativos correctos.Esto simplemente determina si está presionando o apareciendo en la pila, por lo que no complica demasiado el algoritmo dado, simplemente agrega casos para cuando los operadores sucesivos tienen la misma precedencia (es decir, evaluar la pila si se la deja asociativa, empujar a la pila si se asocia correctamente) .

Answer 5

la expresión dada (5 + 2) * 7 podemos tomar como infija

Infix :  (5+2)*7 
Prefix :  *+527 

de lo anterior sabemos que el orden previo y finde taversal del árbol ... y podemos construir fácilmente árbol de esta. Gracias,