método de java para analizar expresiones anidadas

Question

Digamos que he escrito una función para evaluar una operación matemática simple, y tengo alguna entrada del usuario en una cadena como: "1 + [2 + [3 + 4]]" ¿Cómo puedo analizar estos corchetes y extraer primero el texto más interno (3 + 4), evaluarlo y luego analizar las llaves externas (2 + 7)? Tengo una comprensión rudimentaria de la búsqueda y reemplazo de Regex, pero sé que no harán recursiones como esta. Me gustaría un código java básico para hacer esto, no otro jarrón/API más si puedo evitarlo.

Answer 1

La manera más limpia de lograr su objetivo es escribir un Lexer y un analizador para este fin. Escribir un recursive descent parser no es tan difícil de hacer desde el principio para las expresiones aritméticas.

Existen numerosos ejemplos de código en la web. This is an example que podrías usar como inspiración.

El Lexer está allí para normalizar su entrada y para resumirla en una secuencia de tokens. De esta forma, su analizador solo necesita trabajar con tokens en lugar de tener que lidiar además con problemas de espacio en blanco y otras cosas molestas.

Twoexamples para algoritmos de alto nivel que se basan en la pila, another example que muestra un enfoque de descenso recursivo.

Answer 2

creo expresión regular no es una buena opción para conseguir esta funcionalidad

Debe convertir la expresión usuario de sufijo o prefijo de notación y luego construir un árbol de expresión de ellos. Este es un enfoque estándar en CS (idioma en realidad no importa aquí) para resolver este problema de una manera limpia

Answer 3

recursividad funciona bien para ellos:

int parse(String expression){ 
    //use a regex to find an instance of [ followed by numbers/operators, followed by ] 
    //replace it with parse(whatever's inside the brackets) 
    //continue until there are none left 
    //evaluate the string (which should be a sequence of numbers and operators without brackets) 
} 

Answer 4

uso de una pila. Cuando encuentre un corchete abierto, inserte lo que esté trabajando en la pila y comience la nueva expresión. Cuando tocas un corchete de cierre, abre la pila y usa la expresión que acabas de calcular como el siguiente elemento. O, como han dicho los carteles anteriores, usa recursividad o un árbol.

Answer 5

Para Java, puede usar JavaCC para analizador sintáctico/lexer. Lo he usado en numerosos proyectos. Es bastante fácil de usar. Uno de los ejemplos, creo, incluye un análisis aritmético. JavaCC construirá el árbol de sintaxis por el que podría pasar.

Probar la aritmética usando JavaCC daría una buena introducción a la Gramática sin contexto y al concepto de Árbol de sintaxis abstracta. Si está aprendiendo, entonces es un buen paso tomar después de probar lo que @emboss sugirió