El algoritmo shunting yard es un método para analizar (parsing) las ecuaciones matemáticas especificadas en la notación de infijo. En una forma sencilla de entender, si tienes una ecuación matemática escrita de la forma tradicional, como "3 + 4 * (2 - 1)", el algoritmo "shunting yard" es como un organizador que toma esa ecuación y la reordena para que una computadora pueda entenderla y resolverla fácilmente (al final del algoritmo tendría una salida como esta: 3 4 2 * 1 5 - 2 ^ / +). Lo hace utilizando una especie de "pila" para guardar temporalmente las operaciones (como +, -, *, /) y luego las organiza en un orden diferente, ya sea en un formato llamado "notación polaca inversa" (RPN) o en una estructura de árbol (árbol de sintaxis abstracta) que representa la ecuación. El algoritmo fue inventado por Edsger Dijkstra y nombró como algoritmo "shunting yard" (patio de clasificación) porque su operación se asemeja al de un patio de clasificación del ferrocarril.^[1]​^[2]​^[3]​

Al igual que la forma en que las calculadoras evalúan las expresiones en notación polaca inversa (RPN), el algoritmo 'shunting yard' utiliza una 'pila', que es como una torre donde puedes apilar cosas y solo puedes sacar la que está arriba. Las expresiones en infijo, como '3 + 4' o '3 + 4 * (2 - 1)', son la forma en que la mayoría de nosotros escribimos las ecuaciones. Para transformar estas ecuaciones, el algoritmo utiliza dos 'cajas' de texto: una para la ecuación original (la entrada) y otra para la ecuación reordenada (la salida). También tiene una 'pila' donde guarda temporalmente los símbolos de operación (como +, -, *, /) antes de colocarlos en la 'caja' de salida. El algoritmo lee cada símbolo de la ecuación uno por uno y decide qué hacer con él.

1. Leer la entrada: Leer la expresión de entrada símbolo por símbolo, de izquierda a derecha.
2. Si el símbolo es un operando (número o variable): Añadirlo a la cola de salida.
3. Si el símbolo es un operador: Mientras haya operadores en la pila con mayor o igual precedencia que el operador actual, sacar esos operadores de la pila y añadirlos a la cola de salida. Meter el operador actual en la pila.
4. Si el símbolo es un paréntesis izquierdo "(": Meterlo en la pila.
5. Si el símbolo es un paréntesis derecho ")": Mientras no se encuentre un paréntesis izquierdo en la parte superior de la pila, sacar operadores de la pila y añadirlos a la cola de salida. Sacar el paréntesis izquierdo de la pila (pero no añadirlo a la cola de salida). Si después de sacar el paréntesis izquierdo, hay un operador en la parte superior de la pila (por ejemplo, una función), sacarlo también y añadirlo a la cola de salida.
6. Al final de la entrada: Sacar todos los operadores restantes de la pila y añadirlos a la cola de salida.

Entrada: 3+4

1. Agregue 3 a la cola de salida (siempre que un número es leído es agregado a la salida)
2. Empuje (push) el operador + (o su ID) sobre el stack de operadores
3. Agregue 4 a la cola de salida
4. Después de terminar de leer la expresión, retire (pop) todos los operadores que se encuentren en el stack y agréguelos a la salida (en este caso solo hay uno, "+")

Salida: 3 4 +

Esto muestra ya un par de reglas:

• Todos los números son agregados a la salida al momento en que son leídos.
• Al final de la lectura de la expresión, se retira del stack (pop) a todos los operadores que hubieran y se ponen en la cola de salida.

Para analizar la complejidad de tiempo de ejecución de este algoritmo, uno solo tiene que notar que cada token será leído solo una vez, cada número, función, u operador será impreso solo una vez, y cada función, operador o paréntesis será puesto (push) en la pila y retirado (pop) de la pila solo una sola vez - por lo tanto, hay a lo sumo un número constante de operaciones ejecutadas por token, y el tiempo de ejecución es así O(n) - lineal al tamaño de la entrada.

Si se estuviera desarrollando un intérprete de un lenguaje de programación, la salida del algoritmo "shunting yard" (ya sea en notación RPN o en un árbol de sintaxis abstracta) se sometería a un proceso de tokenización y se escribiría en un archivo compilado, listo para su posterior ejecución. Adicionalmente, la conversión de expresiones de infijo a RPN facilita la simplificación de dichas expresiones. Este proceso de simplificación puede implementarse simulando la resolución de la expresión en RPN. Sin embargo, cuando se encuentra una variable cuyo valor es desconocido (nulo), o cuando un operador tiene un operando con valor nulo, tanto el operador como sus operandos se escriben en la salida. Es importante destacar que este método representa una simplificación y puede presentar limitaciones cuando los operandos son, a su vez, operadores. En esencia, esta técnica constituye una optimización similar al plegamiento de constante, aunque no abarca todas las simplificaciones posibles

El algoritmo "shunting yard" es ampliamente utilizado en:

• Compiladores: Para analizar y generar código para expresiones matemáticas.
• Calculadoras: Para evaluar expresiones introducidas por el usuario.
• Intérpretes: Para ejecutar código que contiene expresiones matemáticas.
• Software de hojas de cálculo: Para evaluar fórmulas.

• Simplicidad: El algoritmo es relativamente fácil de entender e implementar.
• Eficiencia: Tiene una complejidad temporal lineal, O(n), donde n es la longitud de la expresión de entrada. Significa que el algoritmo "shunting yard" tarda un tiempo que aumenta de forma proporcional al tamaño de la ecuación que le das. Si la ecuación tiene el doble de símbolos, el algoritmo tardará aproximadamente el doble de tiempo en ordenarla. Esto lo hace bastante rápido incluso para ecuaciones largas.
• Flexibilidad: Puede ser adaptado para manejar diferentes tipos de operadores y funciones.

• Limitaciones: No puede manejar expresiones con ambigüedades inherentes.
• Errores: Requiere una entrada bien formada para funcionar correctamente.

• Parser de precedencia de operadores
• Notación polaca inversa
• Notación de infijo

• Java Applet demonstrating the Shunting yard algorithm
• Parsing Expressions by Recursive Descent Theodore Norvell © 1999–2001. Access date September 14, 2006.
• Infix to RPN Algorithm
• Original description of the Shunting yard algorithm
• Extension to the ‘Shunting Yard’ algorithm to allow variable numbers of arguments to functions
• Free online Algebraic expression to RPN Converter
• Implementación en Java del algoritmo shunting yard