En informática , el algoritmo del patio de maniobras es un método para analizar expresiones matemáticas especificadas en notación infija . Puede producir una cadena de notación de sufijo, también conocida como notación polaca inversa (RPN), o un árbol de sintaxis abstracta (AST). [1] El algoritmo fue inventado por Edsger Dijkstra y se denominó algoritmo "patio de maniobras" porque su funcionamiento se asemeja al de un patio de maniobras de ferrocarril . Dijkstra describió por primera vez el algoritmo Shunting Yard en el informe MR 34/61 de Mathematisch Centrum .
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 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 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 rechaza 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 campo de maniobras se generalizó posteriormente en el análisis de precedencia de operadores .
Una simple conversión
- Entrada: 3 + 4
- Empuje 3 a la cola de salida (cada vez que se lee un número, se empuja a la salida)
- Presione + (o su ID) en la pila del operador
- Empuje 4 a la cola de salida
- Después de leer la expresión, pop los operadores de la pila y les agregan a la salida.
- En este caso solo hay uno, "+".
- Salida: 3 4 +
Esto ya muestra un par de reglas:
- Todos los números se envían a la salida cuando se leen.
- Al final de la lectura de la expresión, saque todos los operadores de la pila y colóquelos en la salida.
Ilustración gráfica
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 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 los precedentes son iguales y el operador se deja asociativo, entonces ese operador se saca 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).
El algoritmo en detalle
Términos importantes: Token , función , asociatividad del operador , precedencia
/ * Esta implementación no implementa funciones compuestas, funciones con número variable de argumentos y 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 en la pila del operador - un operador o 1 : mientras (hay un operador o 2 que no sea el paréntesis izquierdo en la parte superior de la pila de operador, y ya sea o 1 queda asociativo y su prioridad es menor o igual a la de la o 2 , o o 1 es asociativo por la derecha y su prioridad es menor que o 2 ): pop o 2 de la pila de operadores a la cola de salida Empuje o 1 en la pila del operador - un paréntesis izquierdo (es decir, "("): empújelo en 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: sacar el operador de la pila de operadores a la cola de salida / * Si la pila se agota sin encontrar un paréntesis izquierdo, entonces hay paréntesis que no coinciden. * / { 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 : saca la función de la pila de operadores a la cola de salida/ * Después del ciclo while, coloca 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 (izquierda)} 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, 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 insertará 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 el tiempo de ejecución es, por lo tanto, 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, uno simplemente comenzaría desde el final de una cadena de tokens para analizar y trabajar hacia atrás, invertir la cola de salida (por lo tanto, convertir la cola de salida en una pila de salida) y cambiar el comportamiento de paréntesis izquierdo y derecho (recordando que el ahora -el comportamiento de paréntesis izquierdo debería aparecer hasta que encuentre un paréntesis ahora derecho). Y cambiando la condición de asociatividad a la derecha.
Ejemplo detallado
Entrada: 3 + 4 × 2 ÷ (1-5) ^ 2 ^ 3
Operador Precedencia Asociatividad ^ 4 Derecha × 3 Izquierda ÷ 3 Izquierda + 2 Izquierda - 2 Izquierda
El símbolo ^ representa al operador de energía .
Simbólico Acción Salida
(en RPN )
Pila de operadorNotas 3 Agregar token a la salida 3 + Empuje el token para apilar 3 + 4 Agregar token a la salida 3 4 + × Empuje el token para apilar 3 4 × + × tiene mayor precedencia que + 2 Agregar token a la salida 3 4 2 × + ÷ Pop stack a la salida 3 4 2 × + ÷ y × tienen la misma precedencia Empuje el token para apilar 3 4 2 × ÷ + ÷ tiene mayor precedencia que + ( Empuje el token para apilar 3 4 2 × (÷ + 1 Agregar token a la salida 3 4 2 × 1 (÷ + - Empuje el token para apilar 3 4 2 × 1 - (÷ + 5 Agregar token a la salida 3 4 2 × 1 5 - (÷ + ) Pop stack a la salida 3 4 2 × 1 5 - (÷ + Se repite hasta que se encuentra "(" Pila de pop 3 4 2 × 1 5 - ÷ + Descartar paréntesis coincidentes ^ Empuje el token para apilar 3 4 2 × 1 5 - ^ ÷ + ^ tiene mayor precedencia que ÷ 2 Agregar token a la salida 3 4 2 × 1 5 - 2 ^ ÷ + ^ Empuje el token para apilar 3 4 2 × 1 5 - 2 ^ ^ ÷ + ^ se evalúa de derecha a izquierda 3 Agregar token a la salida 3 4 2 × 1 5 - 2 3 ^ ^ ÷ + final Haga estallar toda la pila a la salida 3 4 2 × 1 5-2 3 ^ ^ ÷ +
Entrada: sin (max (2, 3) ÷ 3 × π )
Simbólico Acción Salida =
(en RPN )
Pila de operadorNotas pecado Empuje el token para apilar pecado ( Empuje el token para apilar ( pecado max Empuje el token para apilar max (pecado ( Empuje el token para apilar (max (pecado 2 Agregar token a la salida 2 (max (pecado , ignorar 2 (max (pecado 3 Agregar token a la salida 2 3 (max (pecado ) pop stack a la salida 2 3 (max (pecado Se repite hasta que "(" esté en la parte superior de la pila Pila de pop 2 3 max (pecado Descartar paréntesis coincidentes ÷ Pop stack a la salida 2 3 máx. ( pecado Empuje el token para apilar 2 3 máx. ÷ (pecado 3 Agregar token a la salida 2 3 máximo 3 ÷ (pecado × Pop stack a la salida 2 3 máximo 3 ÷ ( pecado Empuje el token para apilar 2 3 máximo 3 ÷ × (pecado π Agregar token a la salida 2 3 máximo 3 ÷ π × (pecado ) Pop stack a la salida 2 3 máximo 3 ÷ π × ( pecado Se repite hasta que "(" esté en la parte superior de la pila Pila de pop 2 3 máximo 3 ÷ π × pecado Descartar paréntesis coincidentes final Haga estallar toda la pila a la salida 2 3 máximo 3 ÷ π × sin
Ver también
Referencias
- ^ Theodore Norvell (1999). "Análisis de expresiones por descendencia recursiva" . www.engr.mun.ca . Consultado el 28 de diciembre de 2020 .
enlaces externos
- Descripción original de Dijkstra del algoritmo del patio de maniobras
- Implementación de programas alfabetizados en C
- Applet de Java que demuestra el algoritmo del patio de maniobras
- Widget de Silverlight que muestra el algoritmo Shunting Yard y la evaluación de expresiones aritméticas
- Análisis de expresiones por ascendencia recursiva Theodore Norvell © 1999–2001. Fecha de acceso 14 de septiembre de 2006.
- Código Matlab, evaluación de expresiones aritméticas utilizando el algoritmo del patio de maniobras