En informática , el algoritmo de la estación de maniobras es un método para analizar expresiones aritméticas o lógicas, o una combinación de ambas, especificadas en notación infija . Puede producir una cadena de notación posfija, también conocida como notación polaca inversa (RPN), o un árbol de sintaxis abstracta (AST). [1] El algoritmo fue inventado por Edsger Dijkstra , publicado por primera vez en noviembre de 1961, [2] y llamado algoritmo de "estaciones de maniobras" porque su funcionamiento se asemeja al de una estación de maniobras ferroviaria .
Al igual que la evaluación de RPN, el algoritmo de patio de maniobras se basa en una pila . Las expresiones infijas son la forma de notación matemática a la que la mayoría de las personas están acostumbradas, por ejemplo, "3 + 4" o "3 + 4 × (2 − 1)" . Para la conversión hay dos variables de texto ( cadenas ), la entrada y la salida. También hay una pila que contiene operadores que aún no se han añadido a la cola de salida. Para convertir, el programa lee cada símbolo en orden y hace algo en función de ese símbolo. El resultado de los ejemplos anteriores sería (en notación polaca inversa ) "3 4 +" y "3 4 2 1 − × +" , respectivamente.
El algoritmo de la estación de maniobras analizará correctamente todas las expresiones infijas válidas, pero no rechazará todas las expresiones no válidas. Por ejemplo, "1 2 +" no es una expresión infija válida, pero se analizaría como "1 + 2" . Sin embargo, el algoritmo puede rechazar expresiones con paréntesis no coincidentes.
El algoritmo del patio de maniobras se generalizó posteriormente al análisis de precedencia de operadores .
Esto ya muestra un par de reglas:
Ilustración gráfica del algoritmo, utilizando una unión de tres vías . La entrada se procesa un símbolo a la vez: si se encuentra una variable o un número, se copia directamente a la salida a), c), e), h). Si el símbolo es un operador, se coloca en la pila de operadores b), d), f). Si la precedencia del operador es menor que la de los operadores en la parte superior de la pila o las precedencias son iguales y el operador se deja asociativo, entonces ese operador se extrae de la pila y se agrega a la salida g). Finalmente, los operadores restantes se extraen de la pila y se agregan a la salida i).
/* Las funciones a las que se hace referencia en este algoritmo son funciones simples de un solo argumento, como seno, inversa o factorial. */ /* Esta implementación no implementa funciones compuestas, funciones con un número variable de argumentos ni operadores unarios. */mientras haya fichas para leer: leer una ficha Si el token es: - un número : Colóquelo en la cola de salida - una función : Empújelo hacia la pila del operador - un operador o 1 : mientras ( Hay un operador o 2 en la parte superior de la pila de operadores que no es un paréntesis izquierdo, y ( o 2 tiene mayor precedencia que o 1 o ( o 1 y o 2 tienen la misma precedencia y o 1 es asociativo por la izquierda)) ): pop o 2 de la pila de operadores a la cola de salida Empuje o 1 en la pila del operador - a "," : mientras el operador en la parte superior de la pila de operadores no sea un paréntesis izquierdo: Extrae el operador de la pila de operadores y colócalo en la cola de salida - un paréntesis izquierdo (es decir, "("): Empújelo hacia la pila del operador - un paréntesis derecho (es decir, ")"): mientras el operador en la parte superior de la pila de operadores no sea un paréntesis izquierdo: { afirmar que la pila de operadores no está vacía} /* Si la pila se agota sin encontrar un paréntesis izquierdo, entonces hay paréntesis no coincidentes. */ Extrae el operador de la pila de operadores y colócalo en la cola de salida { afirmar que hay un paréntesis izquierdo en la parte superior de la pila de operadores} Saca el paréntesis izquierdo de la pila de operadores y deséchalo. Si hay un token de función en la parte superior de la pila de operadores, entonces : extrae la función de la pila de operadores a la cola de salida/* Después del bucle while, extrae los elementos restantes de la pila de operadores en la cola de salida. */ mientras haya tokens en la pila de operadores: /* Si el token del operador en la parte superior de la pila es un paréntesis, entonces hay paréntesis que no coinciden. */ { afirmar que el operador en la parte superior de la pila no es un paréntesis (izquierdo)} Extrae el operador de la pila de operadores y colócalo en la cola de salida
Para analizar la complejidad del tiempo de ejecución de este algoritmo, solo hay que tener en cuenta que cada token se leerá una vez, cada número, función u operador se imprimirá una vez, y cada función, operador o paréntesis se colocará en la pila y se sacará de ella una vez; por lo tanto, hay como máximo un número constante de operaciones ejecutadas por token, y el tiempo de ejecución es, por tanto, O( n ), lineal en el tamaño de la entrada.
El algoritmo de la estación de maniobras también se puede aplicar para producir notación de prefijo (también conocida como notación polaca ). Para ello, simplemente se debe empezar desde el final de una cadena de tokens que se analizarán y trabajar hacia atrás, invertir la cola de salida (convirtiendo así la cola de salida en una pila de salida) e invertir el comportamiento del paréntesis izquierdo y derecho (recordando que el comportamiento del paréntesis ahora izquierdo debe aparecer hasta que encuentre un paréntesis ahora derecho). Y cambiar la condición de asociatividad a derecha.
Entrada: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3
El símbolo ^ representa el operador de potencia .
Entrada: pecado ( max ( 2, 3 ) ÷ 3 × π )