Algoritmo de patio de maniobras

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 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 nombrado porque su funcionamiento se asemeja al de una estación de maniobras ferroviarias .

Al igual que la evaluación de RPN, el algoritmo 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 la gente está acostumbrada, 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 almacena los 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 realiza una acción en función de ese símbolo. El resultado para 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 analiza correctamente todas las expresiones infijas válidas, pero no rechaza todas las expresiones inválidas. Por ejemplo, "1 2 +" no es una expresión infija válida, sino que se analizaría como "1 + 2" . Sin embargo, el algoritmo puede rechazar expresiones con paréntesis incorrectos.

El algoritmo de maniobras de clasificación se generalizó posteriormente en un análisis de precedencia de operadores .

1. Entrada: 3 + 4
2. Se añade el número 3 a la cola de salida (cada vez que se lee un número, se añade a la salida).
3. Empuje + (o su ID) a la pila del operador.
4. Empujar 4 a la cola de salida
5. Después de leer la expresión, extraiga los operadores de la pila y agréguelos a la salida.

   En este caso solo hay uno, "+".

6. Salida: 3 4 +

Esto ya muestra un par de reglas:

• Todos los números se envían a la salida cuando se leen.
• Al finalizar la lectura de la expresión, extraiga todos los operadores de la pila y colóquelos en la salida.

Ilustración gráfica del algoritmo, utilizando una bifurcación ferroviaria de tres vías . La entrada se procesa símbolo por símbolo: 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 inserta 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 si las precedencias son iguales y el operador es asociativo izquierdo, 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).

mientras haya fichas para leer: leer un token si el token es: - un número : colócalo en la cola de salida - una función : empújalo a 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)) ): Extraer o 2 de la pila de operadores a la cola de salida. empuja 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újalo a 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 de operadores no está vacía} /* Si la pila se agota sin encontrar un paréntesis izquierdo, entonces hay paréntesis que no coinciden. */ 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 } Extrae el paréntesis izquierdo de la pila de operadores y descártalo. 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 y colócala en la cola de salida. /* Después del bucle while, extraiga los elementos restantes de la pila de operadores y colóquelos 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 temporal de este algoritmo, basta con observar 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 insertará en la pila y se extraerá de ella una vez; por lo tanto, se ejecuta como máximo un número constante de operaciones por token, y el tiempo de ejecución es, por consiguiente, 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 prefija (también conocida como notación polaca ). Para ello, bastaría con comenzar desde el final de una cadena de tokens a analizar y trabajar hacia atrás, invertir la cola de salida (convirtiéndola así en una pila de salida) e invertir el comportamiento de los paréntesis izquierdo y derecho (recordando que el comportamiento del paréntesis ahora izquierdo debe eliminar elementos hasta que encuentre un paréntesis ahora derecho), asegurándose de 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 × π )

• Analizador de precedencia de operadores
• Permutación ordenable mediante pila

• Descripción original de Dijkstra del algoritmo del patio de maniobras
• Implementación de programas de alfabetización en C
• Demostración del algoritmo de patio de maniobras en Rust
• Applet de Java que demuestra el algoritmo de la estación de maniobras.
• Análisis sintáctico de expresiones mediante descenso recursivo. Theodore Norvell © 1999–2001. Fecha de acceso: 14 de septiembre de 2006.
• Código Matlab para la evaluación de expresiones aritméticas mediante el algoritmo de la estación de maniobras.