Cómo analizar una expresión algebraica

Question

Voy a hacer un programa que puede analizar una expresión algebraica.
Por ejemplo:
<?php echo cal ('5*5+2*2'); ?>
Mi programa sabrá que se multiplicará 5 con 5 y 2 con 2 en primer lugar, a continuación, además de ellos. Quiero analizar por mí mismo, y no por php.

Answer 1

Puede tomar la expresión 'infija' y utilizando una pila, convertirlo en un 'prefijo' o la expresión 'de sufijo' para decidir el orden de la operación (Paréntesis, Exponenciación, multiplicación o división, suma o resta).

Por ejemplo la expresión ([5] [*] [5] [+] [2] [*] [2]) se transformaría en la expresión postfix [5] [5] [*] [2] [ 2] [*] [+]. esta expresión 'postfix' ahora se puede leer como 'cinco y cinco multiplicado, de dos en dos multiplicado, y después se añadió junto' que preserve el orden de operación.

Otra forma de pensar de la '/ postfix prefijo' idea es la de múltiples pilas. Cuando se encuentre con el número 5, empujarlo en la pila principal. Cuando se encuentra con el símbolo se multiplican, almacenarlo en la pila secundaria. Al llegar a la siguiente 5, empujarlo en la pila primaria, a continuación, el pop todos los elementos fuera de la pila secundaria y empujarlos hacia su pila primaria.

Una vez que tenga los operadores y operandos en el orden correcto, es una cuestión de hacer estallar los elementos de la pila y luego evaluarlas.

Recuerdo averiguar este problema en mi 102 Informática curso en la universidad. ¿Estás haciendo esto por diversión, o simplemente tratando de averiguarlo?

Answer 2

Yo iba a sugerir que se mire recursiva descenso analizadores , pero parece que las cosas han cambiado en desde la última vez hice esto en la década de 1980 a mediados. Parece que una de análisis de expresión Gramática es el camino a seguir ahora si se quiere entender la teoría detrás todo.

Si no le importa nada acerca de la teoría, eso está bien: la aplicación de los medios teoría de que usted va a terminar de escribir un analizador descendente recursivo de todos modos, por lo que sólo puede hacer eso: -)