programar - Análisis de una expresión aritmética y construcción de un árbol en Java
programar un arbol binario de busqueda en java (5)
Asumiendo que esto es algún tipo de tarea y quieres hacerlo tú mismo ..
Lo hice una vez, necesitas una pila
Entonces, lo que haces por 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 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 pila al anterior (o al comienzo del archivo.
Debido a que tu pila ahora contiene 5 + 2 * 7, cuando la 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 correcto.
Si se ordenó de la otra manera: 5 * 2 + 7, presionarías hasta llegar a una pila 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.
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 pila 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).
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 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) .
Varias opciones para usted:
Reutilizar un analizador de expresiones 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).
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 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.
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 sintaxis comunes.
Actualización: Aquí hay 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.
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,