Problemas para entender qué hacer con la producción del algoritmo de yardas de derivación
-
27-10-2019 - |
Pregunta
He estado mirando la página wiki: http://en.wikipedia.org/wiki/shunting-yard_algorithm
He usado el ejemplo de código para construir la primera parte, básicamente puedo cambiar:
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
dentro 3 4 2 * 1 5 − 2 3 ^ ^ / +
Pero no sé cómo usar 3 4 2 * 1 5 − 2 3 ^ ^ / +
para obtener 3.00012207
Y el código de ejemplo y la explicación en Wiki no tienen ningún sentido para mí.
¿Alguien podría explicar cómo evaluar 3 4 2 * 1 5 − 2 3 ^ ^ / +
y producir la respuesta. Gracias por adelantado. No necesito un ejemplo de código solo una buena explicación o un desglose de un ejemplo.
No es que importe, pero estoy trabajando .NET C#.
Solución
El propósito del algoritmo de patio de derivación es que su salida está en Notación de polaco inverso, que es sencillo para evaluar:
- crear una pila para mantener valores
- Mientras queda la entrada de notación de polaco inverso:
- Leer un elemento de entrada
- Si es un valor, empújalo en la pila
- De lo contrario, es una operación; Valores POP desde la pila, realice la operación en esos valores, presione el resultado hacia atrás
- Cuando no queda entrada, si la expresión estaba bien formada, debería haber exactamente un valor en la pila; Este es el resultado evaluado.
Otros consejos
La notación posterior a la fijación es cómo se hace las matemáticas en, por ejemplo, una calculadora HP.
Mantenga una pila, cada vez que obtenga un número, agréguelo a la parte superior. Siempre que obtenga un operador, consuma entradas desde la parte superior y luego agregue el resultado a la parte superior
token stack
*empty*
3 3 //push numbers...
4 3 4
2 3 4 2
* 3 8 //remove 4 and 2, add 4*2=8
1 3 8 1
5 3 8 1 5
- 3 8 -4
2 3 8 -4 2
3 3 8 -4 2 3
^ 3 8 -4 8
... ...
Procesar los elementos 3 4 2 * 1 5 − 2 3 ^ ^ / +
De izquierda a derecha de la siguiente manera:
- Inicialice una pila para mantener los números.
- Si el elemento es un número, empújalo en la pila.
- Si el elemento es un operador, retire los dos elementos superiores de la pila, aplique el operador a esos dos elementos y presione el resultado en la pila.
Cuando llegue al final, la pila debe tener un solo elemento que sea el resultado.
Veo que llego un poco tarde a la fiesta.
Vi la pregunta y salí a una tangente escribiendo un par de tareas para el código Rosetta. Simplemente sucede que esta tarea Podría ser lo que buscas. Da una tabla anotada de lo que sucede al calcular el valor de una expresión de RPN, token por token.
Aquí hay una muestra de su salida:
For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +'
TOKEN ACTION STACK
3 Push num onto top of stack 3
4 Push num onto top of stack 3 4
2 Push num onto top of stack 3 4 2
* Apply op to top of stack 3 8
1 Push num onto top of stack 3 8 1
5 Push num onto top of stack 3 8 1 5
- Apply op to top of stack 3 8 -4
2 Push num onto top of stack 3 8 -4 2
3 Push num onto top of stack 3 8 -4 2 3
^ Apply op to top of stack 3 8 -4 8
^ Apply op to top of stack 3 8 65536
/ Apply op to top of stack 3 0.0001220703125
+ Apply op to top of stack 3.0001220703125
The final output value is: '3.0001220703125'