algoritmo de Dijkstra y funciones

Question

la pregunta es: supongamos que tengo una función de entrada como sin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B) especificado con una BNF, voy a analizar la entrada utilizando el algoritmo de descenso recursivo, y entonces, ¿cómo puedo usar el cambio o algoritmo de Dijkstra para manejar esta función dada? Necesito para ejecutarlo con el pecado | cos | sqrt | En donde el algoritmo de Dijkstra debe hacer el trabajo.

EDIT: Puede ser que debe preguntar también: ¿Cuál es la mejor práctica o estructura de datos para representar función dada?

EDIT: conjunto de entrada se puede adquirir como:

C 0.01 .01 .02 .04 .08 .02 .02 .04 
A .016 .008 .116 .124 .147 .155 .039 .023  
D .012 .025 .05 .1 .1 .1 .025 .012000 .012
B .007 .007 .015 .022 .029 .036 .044 .051 .058 .066 .073 .080 

EDIT: Estación de clasificación es el algoritmo para convertir la función de entrada a RPN, pero ¿cómo puedo extenderlo a aceptar otra función como el pecado | cos | sqrt | En? No descenso recursivo proporciona una extensión a Estación de clasificación requiere?

Answer 1

supongo que estamos hablando de Dijkstra Estación de clasificación algoritmo?

Para evaluar la notación polaca inversa (salida del patio de maniobra), se utiliza normalmente una pila.

Estación de clasificación fue ideado para hacer el análisis de Algol creo, y creo que se supone que funciona con cualquier función (ya sea fijo o variable de argumentos).

Esta es una entrada de blog que explica con más detalle: http://www.kallisti.net.nz/blog/2008/02/extension-to-the-shunting- patio-algoritmo-a-Allow-variable-número-de-argumentos a funciones /

Answer 2

No veo Dijkstra aquí, ya que se utiliza para encontrar el camino más corto en un grafo con pesos no negativos.

En el caso de que se habla de un analizador sintáctico descendente recursivo, que es del tipo LL (k) y se define por una gramática similar a

expression ::= term + term | term - term
term ::= factor * factor | factor / factor
factor ::= ident | number

number ::= digit | digit number
digit ::= 0 | 1 | 2 ...

la mejor estructura de datos para almacenar este tipo de información por lo general es un árbol de sintaxis abstracta que es un árbol que replica la estructura del código se analiza. En ti ejemplo, se necesitaría una estructura diferente o clase para diversas piezas de código: BinaryOperation, Ident, Number, UnaryOperation, FunctionCall termina encima de tener algo así como

                         BinaryOperation +
                          |            |
                                     BinaryOperation *
                                      |            |
                                    Number       BinaryOperation +
                                      |           |
                                     0.756     BinOp *
                                               |    |
                                             Ident Ident
                                               |    |
                                               C    D

EDIT: No sabía que yardas de maniobras fue inventado por Dijkstra! Por cierto que es un algoritmo bastante fácil como Morón explicó .. que nunca se deja de aprender algo nuevo!

Answer 3

antlr con una gramática similar a la que proporcionan Jack. Debería ser suficiente para crear un buen programa de análisis en varios idiomas: Java / C / C ++ / Python / etc. Lea algunos ejemplos y tutoriales. Debe utilizar ANTLRWorks para la verificación de la expresión más rápido.