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
![Shunting yard.svg](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/2/24/Shunting_yard.svg/400px-Shunting_yard.svg.png)
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, entonces : empújelo a la cola de salida. de lo contrario, si el token es una función, entonces : empújelo en la pila del operador de lo contrario, si el token es un operador, entonces : while ((hay un operador en la parte superior de la pila de operadores) y ((el operador en la parte superior de la pila de operadores tiene mayor precedencia) o (el operador en la parte superior del operador la pila tiene la misma precedencia y el token es asociativo a la izquierda)) y (el operador en la parte superior de la pila de operadores no es un paréntesis a la izquierda)): pop operadores de la pila de operadores en la cola de salida. empújelo sobre la pila del operador. de lo contrario, si el token es un paréntesis izquierdo (es decir, "("), entonces : empújelo sobre la pila del operador. de lo contrario, si el token es un paréntesis derecho (es decir, ")"), entonces : mientras que el operador en la parte superior de la pila de operadores no es un paréntesis izquierdo: saca 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. * / si hay un paréntesis izquierdo en la parte superior de la pila de operadores, entonces : saque el operador de la pila de operadores y deséchelo si hay un token de función en la parte superior de la pila de operadores, entonces : coloca la función de la pila de operadores en la cola de salida./ * Después del ciclo while, si la pila del operador no es nula, sacar todo a la cola de salida * / si no hay más tokens para leer entonces : mientras todavía hay tokens del operador en la pila: / * Si el token del operador está en la parte superior del pila es un paréntesis, luego hay paréntesis que no coinciden. * / saca el operador de la pila de operadores a la cola de salida.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 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, 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 voltear el comportamiento de paréntesis izquierdo y derecho (recordando que el ahora -el comportamiento del paréntesis izquierdo debería aparecer hasta que encuentre un paréntesis ahora a la derecha). 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 Saque toda la pila para imprimir 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 Saque toda la pila para imprimir 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