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.