Algoritmo shunting yard

El algoritmo shunting yard es un método para analizar (parsing) las ecuaciones matemáticas especificadas en la notación de infijo. Puede ser utilizado para producir la salida en la notación polaca inversa (RPN) o como árbol de sintaxis abstracta (AST). 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.

Como la evaluación del RPN, el algoritmo shunting yard está basado en el stack. Las expresiones de infijo son la forma de matemáticas a la que la mayoría de la gente está acostumbrada, por ejemplo 3+4 ó 3+4*(2-1). Para la conversión hay dos variables de texto (strings), la entrada y la salida. Hay también un stack que guarda los operadores que todavía no se han añadido a la cola de salida. Para hacer la conversión, el programa lee cada símbolo en orden y hace algo basado en ese símbolo.

Entrada: 3+4

Salida: 3 4 +

Esto muestra ya un par de reglas:

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 usted estuviera escribiendo un intérprete, esta salida sería tokenizada y escrita a un archivo compilado para ser interpretado posteriormente. La conversión de infijo a RPN puede también permitir una más fácil simplificación de expresiones. Para hacer esto, actúe como si usted estuviera resolviendo la expresión de RPN, sin embargo, siempre que usted llegue a una variable su valor es nulo, y siempre que un operador tenga un valor nulo, él y sus parámetros son escritos a la salida (esto es una simplificación, los problemas se presentan cuando los parámetros son operadores). Cuando un operador no tiene ningún parámetro nulo su valor simplemente puede ser escrito a la salida. Este método no incluye todas las simplificaciones posibles; es más una optimización de plegamiento de constante.