En informática , el algoritmo del patio 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 postfija, 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 lo denominó algoritmo de "patio de maniobras" porque su funcionamiento se asemeja al de un patio de maniobras de ferrocarril.
Al igual que la evaluación de RPN, el algoritmo del patio de maniobras se basa en pilas . Las expresiones infijas son la forma de notación matemática a la que la mayoría de la gente está acostumbrada, por ejemplo "3 + 4" o "3 + 4 × (2 − 1)" . Para la conversión existen dos variables de texto ( cadenas ), la entrada y la salida. También hay una pila que contiene operadores que aún no se han agregado a la cola de salida. Para convertir, el programa lee cada símbolo en orden y hace algo basado en 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 del patio 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 que no coinciden.
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 un cruce ferroviario 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 empuja a 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 queda asociativo a la izquierda, entonces ese operador se saca de la pila y se agrega a la salida g). Finalmente, los operadores restantes se sacan 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 hay tokens para leer: leer una ficha si el token es: - un número : ponerlo 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 izquierda)) ): pop o 2 de la pila del operador a la cola de salida Empuje o 1 hacia la pila del operador. - a "," : mientras que el operador en la parte superior de la pila de operadores no es un paréntesis izquierdo: saque el operador de la pila de operadores a la cola de salida - un paréntesis izquierdo (es decir, "("): empújelo hacia la pila del operador - un paréntesis derecho (es decir, ")"): mientras que el operador en la parte superior de la pila de operadores no es un paréntesis izquierdo: { afirmar que la pila del operador no está vacía} /* Si la pila se agota sin encontrar un paréntesis izquierdo, entonces hay paréntesis que no coinciden. */ saque el operador de la pila de operadores a la cola de salida { afirmar que hay un paréntesis izquierdo en la parte superior de la pila de operadores} saque el paréntesis izquierdo de la pila de operadores y deséchelo Si hay un token de función en la parte superior de la pila del operador, entonces : sacar la función de la pila del operador a la cola de salida/* Después del ciclo while, coloque los elementos restantes de la pila del operador en la cola de salida. */ mientras hay tokens en la pila del operador: /* 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)} sacar el operador de la pila de operadores a la cola de salida
Para analizar la complejidad del tiempo de ejecución de este algoritmo, sólo 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 salió de la pila una vez; por lo tanto, hay como máximo un número constante de operaciones ejecutadas por token y, por lo tanto, el tiempo de ejecución es O ( n ), lineal en el tamaño de la entrada.
El algoritmo del patio de maniobras también se puede aplicar para producir notación de prefijo (también conocida como notación polaca ). Para hacer esto, simplemente se comenzaría desde el final de una cadena de tokens a analizar y se trabajaría hacia atrás, se invertiría la cola de salida (convirtiendo así la cola de salida en una pila de salida) y se invertiría el comportamiento de los paréntesis izquierdo y derecho (recordando que ahora -el comportamiento del paréntesis izquierdo debería aparecer hasta que encuentre un paréntesis ahora derecho). Y cambiando la condición de asociatividad a la derecha.
Entrada: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3
El símbolo ^ representa al operador de energía .
Entrada: pecado ( max ( 2, 3 ) ÷ 3 × π )