Analizando ecuaciones matemáticas básicas para software educativo para niños?

Question

Inspirado por un recent TED talk, quiero escribir una pequeña pieza de software educativo. El investigador creó pequeñas computadoras en miniatura en forma de bloques llamados "Siftables".

alt text http://images.ted.com/images/ted/tedindex/embed-posters/DavidMerrill-2009.embed_thumbnail.jpg
[David Merril, inventor - with Siftables in the background.]

Había muchas aplicaciones que usó en los bloques, pero mi favorito fue cuando cada bloque era un número o símbolo de la operación básica. Luego podría volver a organizar los bloques de números o símbolos de operación en una línea, y se mostraría una respuesta en otro bloque graduable.

alt text http://i44.tinypic.com/m7us6g.png

Por lo tanto, he decidido que quería implementado una versión de software de "Matemáticas Siftables" en una escala limitada como mi proyecto final de un curso de CS que estoy tomando.

¿Cuál es la forma generalmente aceptada para analizar e interpretar una cadena de expresiones matemáticas, y si son válidas, realizar la operación?

¿Es este un caso en el que debería implementar un analizador/analizador completo? Me imagino que la interpretación de expresiones matemáticas básicas sería un problema casi común en informática, así que estoy buscando la forma correcta de abordarlo.

Por ejemplo, si mis Math Siftable bloques donde dispuestas como:

[1 ] [+ ] [2 ]

Esto sería una secuencia válida y me gustaría realizar la operación necesaria para llegar a "3".

Sin embargo, si el niño fuera a arrastrar varios bloques de operación en conjunto, tales como:

[2 ] [\ ] [\ ] [5 ]

es obvio que sería válido.

En última instancia, quiero ser capaz de analizar e interpretar cualquier cantidad de cadenas de operaciones con los bloques que el usuario puede arrastrar juntos. ¿Alguien puede explicarme o señalarme recursos para analizar expresiones matemáticas básicas?

Prefiero la mayor cantidad de respuestas idiomáticas posibles.

Answer 1

Puede consultar el Shunting Yard Algorithm. La página enlazada de Wikipedia tiene mucha información y enlaces a varios ejemplos del algoritmo.

Básicamente, dada una expresión en notación matemática infija, devuelve una notación polaca AST o inversa, cualquiera que sea su preferencia.

Este page es bastante bueno. También hay preguntas couplerelated en SO.

Answer 2

En muchos lenguajes modernos hay métodos para evaluar expresiones de cadenas aritméticas. Por ejemplo, en Python

>>> a = '1+3*3'  
>>> eval(a)   
10  

Puede utilizar el control de excepciones para capturar la sintaxis no válida.

alternativa, se puede construir árboles de expresión aritmética, hay algunos ejemplos de estos aquí en SO: Expression Trees for Dummies.

Answer 3

Como se ha señalado anteriormente, me gustaría convertir la cadena normal (notación infija) a una solución después de la expresión.

Luego, dada la expresión posterior a la corrección, es fácil analizar y evaluar la expresión. Por ejemplo, agregue los operandos a una pila y cuando encuentre un operador, saque los valores de la pila y aplique el operador a los operandos. Si su código para convertirlo a una expresión de corrección de publicación es correcto, no debería tener que preocuparse por el orden de las operaciones ni nada de eso.

La mayoría del trabajo en este caso probablemente se haría en la conversión. puede almacenar el formulario convertido en una lista o matriz para facilitar el acceso, de modo que no necesite volver a analizar cada valor nuevamente.

Answer 4

Usted dice que varios operadores en una fila no son válidos. Pero piense en:

5 + -2 

Cuál es perfectamente válido.

La gramática de expresión más básica es como:

Expression = Term | Expression, AddOp, Term 
Term  = Factor | Term, MulOp, Factor 
Factor  = Number | SignOp, Factor | '(', Expression, ')' 

AddOp  = '+' | '-' 
MulOp  = '*' | '/' 
SignOp  = '+' | '-' 

Number  = Digit | Number, Digit 
Digit  = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 

una vez me escribió un simple analizador de expresiones/evaluador ligera (cadena en número a cabo) que podría manejar variables y funciones. El código está en Delphi pero no debería ser tan difícil de traducir. Si está interesado, puedo poner el código fuente en línea.

Answer 5

Otra nota es que hay muchas bibliotecas de análisis disponibles que una persona puede usar para realizar esta tarea. No es trivial escribir un buen analizador de expresiones desde cero, por lo que recomendaría consultar una biblioteca.

Trabajo para Singular Systems que se especializa en componentes matemáticos. Ofrecemos dos analizadores matemáticos Jep Java y Jep.Net que pueden ayudarlo a resolver su problema. ¡Buena suerte!

Answer 6

Para esta audiencia, le gustaría dar un mensaje de error bastante diferente a los programadores utilizados para mensajes como "Error de sintaxis: inesperado"/"en posición foo". Traté de hacer algo mejor para la educación applets aquí:

http://github.com/darius/expr

Las ideas principales: van a longitudes inusuales para encontrar una edición mínima restaurar parsability (práctica ya que las expresiones de entrada no son páginas de largo), y generan una explicación más simple en inglés de lo que el analizador está atascado.