Análisis de una expresión aritmética y construcción de un árbol en Java

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

(5+2)*7 

El árbol de resultados debería verse así:

  * / \ + 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, por lo que puedo realizar otras funciones más adelante. Además, el operador negativo ‘-‘ solo puede tener un hijo, y para representar ‘5-2’, debe ingresarlo como 5 + (-2).

Se requerirá cierta validación en 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 stack de tokens, si eso va a ser útil para esto.

Apreciaría cualquier ayuda en absoluto. Gracias 🙂

(Leí 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, te agradecería si podría proporcionar algunos tutoriales / enlaces útiles para ellos).

La “Introducción de cinco minutos a 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).

Asumiendo que esto es algún tipo de tarea y quieres hacerlo tú mismo ..

Lo hice una vez, necesitas una stack

Entonces, lo que haces por el ejemplo es:

     analizar qué hacer?  La stack parece
       (empújalo en la stack (
       5 push 5 (, 5
       + push + (, 5, +
       2 push 2 (, 5, +, 2
       ) evaluar hasta (7            
       * push * 7, *
       7 push 7 +7, *, 7
       eof evaluar hasta los primeros 49

Los símbolos como “5” o “+” solo pueden almacenarse como cadenas u objetos simples, o puede almacenar el + como un objeto + () sin establecer los valores y establecerlos 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

tienes que presionar 5 push + push 2 next op es mayor precedencia así que empuja también, luego presiona los tres. Cuando encuentre ya sea a) o el final del archivo o un operador con precedencia inferior o igual, usted comienza a calcular la stack al anterior (o al comienzo del archivo.

Debido a que tu stack ahora contiene 5 + 2 * 7, cuando la evalúas, sacas el 2 * 7 primero e insertas el * (2,7) nodo resultante en la stack, luego, una vez más, evalúas los tres elementos superiores en la stack ( 5 + * nodo) para que el árbol salga correcto.

Si se ordenó de la otra manera: 5 * 2 + 7, presionarías hasta llegar a una stack con “5 * 2”, 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, y en ese punto lo evaluarías.

Esto significa que tiene una “precedencia actual 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 siguiente operador es <= su precedencia actual.

si “)” se considera prioridad 4, puede tratarlo como otros operadores, excepto que elimina la coincidencia “(“, una prioridad más baja no.

Quería responder a la respuesta de Bill K., pero carezco de la reputación de agregar un comentario allí (en realidad, esta es la 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 la asociatividad del operador ; a saber, 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 

Normalmente, la división y la resta se consideran asociativas de la izquierda (es decir, el 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 stack, 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 stack si se la deja asociativa, empujar a la stack si se asocia correctamente) .

Varias opciones para usted:

  1. Reutilizar un analizador de expresiones existente. Eso funcionaría si eres flexible en syntax 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. Escribe tu 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 está fuera del scope de esta respuesta. Si sigue esta ruta, encuentre un buen libro sobre diseño de comstackdores. 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 aunque tengas 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 la entrada mal formada (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 syntax comunes.

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

Contenido de org.eclipse.sapphire / plugins / org.eclipse.sapphire.modeling / src / org / eclipse / zafiro / modelado / el / parser / internal / ExpressionLanguageParser.jj

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

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

de lo anterior, sabemos el preorden y la tara de árbol inorder … y podemos construir fácilmente un árbol a partir de esto. Gracias,