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).

Para la conversión hay dos variables de texto (strings), la entrada y la salida.

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.

Ilustración gráfica del algoritmo usando un cruce de ferrocarril de tres vías. La entrada es procesada un símbolo a la vez, si es encontrada una variable o un número, es directamente copiado a la salida b), d), f), h). Si el símbolo es un operador, es colocado en el stack (push) c), e), sin embargo, si su precedencia es menor que la del operador en el tope del stack o las precedencias son iguales y el operador es asociativo por la izquierda, entonces aquel operador es sacado del stack (pop) y añadido a la salida g). Finalmente, los operadores restantes son sacados del stack (pop) y agregados a la salida.