1) El algoritmo Shunting Yard fue inventado por el científico informático holandés (y un físico teórico por educación) Edsger W. Dijkstra en 1961 como un método para transformar una expresión matemática arbitraria expresada en forma infija en una expresión equivalente representada en prefijo o postfix o una forma de árbol de sintaxis abstracta.
En la práctica, la traducción anterior normalmente constituye el primer paso del cálculo general de dos pasos del valor de la expresión dada. Si designamos una expresión (aritmética por ahora) representada en una notación infija como [math] E_ {in} [/ math]:
[math] \ displaystyle E_ {in} = 1 + 2 \ tag * {} [/ math]
- ¿Cómo funciona el código de visualización en Windows Media Player?
- ¿Por qué medios se puede realizar una regresión de alta dimensión (#características >> #observaciones) que no sea la regularización (LASSO, regresión de cresta, etc.)?
- ¿Google está bajando su barra de contratación para ingenieros?
- Cómo clonar una máquina virtual VMware en otra máquina virtual usando Clonezilla
- Cómo explicar la memoria virtual a un laico
entonces su correspondiente forma de prefijo [math] E_ {pr} [/ math] será:
[matemáticas] \ displaystyle E_ {pr} = +12 \ etiqueta * {} [/ matemáticas]
mientras que su forma de postfix [math] E_ {po} [/ math] será:
[matemáticas] \ displaystyle E_ {po} = 12+ \ tag * {} [/ matemáticas]
Observamos que en la notación de prefijo el operador precede a sus operandos, mientras que en la notación de postfijo , el operador sigue sus operandos si aceptamos que las expresiones se leen en una dirección de izquierda a derecha.
El orden de ejecución de los operadores en una expresión infija puede controlarse / modificarse con paréntesis (tradicionalmente) mientras que en las expresiones de prefijo / postfijo ese orden es absoluto: está determinado únicamente por la posición de los operadores dentro de la expresión a medida que los operadores se ejecutan en la ubicación donde se encuentran Como tal, las anotaciones de prefijo / postfix no requieren paréntesis. Esta es, esencialmente, la razón del infijo para la transformación de prefijo / postfijo que se logra con dos tipos de contenedores lineales: una pila, que se usa solo para almacenar operadores, y una cola, que se usa para almacenar ambos: operadores y operandos.
Una vez que una expresión infija se ha transformado en una forma de prefijo / postfijo en la primera pasada, el valor general de esa expresión se puede calcular en la segunda pasada con la ayuda de los mismos contenedores, con la excepción del tipo de elementos almacenados en la pila se invierte: ahora se usa una pila para almacenar operandos solamente.
La mecánica interna de este algoritmo se describe en profundidad en este tutorial, establecido en el contexto del concepto de construcción de software incremental.
Hay un programa auxiliar (en la parte inferior de esta sección) que visualiza la operación del algoritmo Shunting-Yard y le permite: ingresar una expresión aritmética entre paréntesis arbitraria en forma de infijo; conviértalo en forma de prefijo o postfix; reproducir todo el proceso en cámara lenta; atestigüe cómo se genera un cálculo exitoso o errores (el código fuente completo del programa se puede obtener de este repositorio de GitHub).
2) El verdadero poder o la esencia del algoritmo Shunting-Yard sale a la luz una vez que nos damos cuenta de que con pequeños ajustes decorativos se puede reutilizar para hacer cosas que son similares en naturaleza pero diferentes en detalles técnicos menores.
Por ejemplo, tomemos una oración ordinaria en inglés [math] S [/ math]:
S = "la informática es divertida"
y una formación casi de oración que podemos llamar una regla [matemáticas] R [/ matemáticas]:
R = "computadora y diversión"
Ahora afirmamos que tiene mucho sentido arrastrar o rastrear la oración [matemáticas] S [/ matemáticas] a través de la regla [matemáticas] R [/ matemáticas] con el objetivo de obtener una respuesta booleana, verdadera o falsa, a la siguiente pregunta :
¿La oración S pasa la regla R?
Evidentemente lo hace, ya que [math] S [/ math] contiene ambas palabras, “computer” y “fun”, como lo exige la regla [math] R [/ math] en la que el carácter de signo representa el operador booleano AND . Ahora, esta oración no pasa [matemáticas] R [/ matemáticas]:
"La informática es increíble"
ya que solo una de las dos palabras requeridas, “computadora”, está presente. Sin embargo, la misma oración pasará la siguiente regla [matemáticas] R [/ matemáticas]:
R = "computadora | divertido"
en el que el carácter de tubería representa el operador OR booleano (inclusive).
Y el algoritmo Shunting-Yard puede usarse para obtener la respuesta a la pregunta anterior como se demuestra en este tutorial.
Por último, observamos que en este contexto particular también podemos implementar el operador booleano de negación NOT (con, digamos, un signo de exclamación!) Y un operador XOR exclusivo booleano (con, digamos, un carácter cap ^) como un acceso directo para expresión que usa los operadores booleanos stock AND y OR para que en lugar de:
(p &! q) | (! p & q)
simplemente decimos:
p ^ q
y así.
