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.

Una conversión sencilla

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.

Entrada: 3+4

Agregue 3 a la cola de salida (siempre que un número es leído es agregado a la salida)
Empuje (push) el operador + (o su ID) sobre el stack de operadores
Agregue 4 a la cola de salida
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.

El algoritmo en detalle

Mientras haya tokens a ser leídos:

Lea un token.
Si el token es un número, entonces agregúelo a la cola de salida.
Si el token es un token de función, entonces póngalo (push) sobre la pila.
Si el token es un separador de un argumento de función (ej., una coma):

Hasta que el token en el tope de la pila sea un paréntesis abierto, retire (pop) de la pila a los operadores y póngalos en la cola de salida. Si no es encontrado ningún paréntesis abierto, el separador fue colocado mal o los paréntesis fueron mal emparejados.

Si el token es un operador, o₁, entonces:

mientras que haya un operador, o₂, en el tope de la pila (esto excluye el paréntesis abierto), y

o₁ es asociativo izquierdo y su precedencia es menor que (una precedencia más baja) o igual a la de o₂, ó

o₁ es asociativo derecho y su precedencia es menor que (una precedencia más baja) que la de o₂,

retire (pop) de la pila el o₂, y póngalo en la cola de salida;

ponga (push) o₁ en el tope de la pila.

Si el token es un paréntesis abierto, entonces póngalo en la pila.
Si el token es un paréntesis derecho:

Hasta que el token en el tope de la pila sea un paréntesis abierto, retire (pop) a los operadores de la pila y colóquelos en la cola de salida.
Retire (pop) el paréntesis abierto de la pila, pero no lo ponga en la cola de salida.
Si el token en el tope de la pila es un token de función, póngalo (pop) en la cola de salida.
Si la pila se termina sin encontrar un paréntesis abierto, entonces hay paréntesis sin pareja.

Cuando no hay más tokens para leer:

Mientras todavía haya tokens de operadores en la pila:

Si el token del operador en el tope de la pila es un paréntesis, entonces hay paréntesis sin la pareja correspondiente.
retire (pop) al operador y póngalo en la cola de salida.

Fin.

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.

Ejemplo detallado

Entrada: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Operador	Precedencia	Asociatividad
^	4	de derecha a izquierda
*	3	de izquierda a derecha
/	3	de izquierda a derecha
+	2	de izquierda a derecha
-	2	de izquierda a derecha

Entrada: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Token	Acción	Salida (en RPN)	Stack de operadores	Notas
3	agrega token a la salida	3
+	Push token al stack	3	+
4	agrega token a la salida	3 4	+
*	Push token al stack	3 4	* +	* tiene mayor precedencia que +
2	agrega token a la salida	3 4 2	* +
/	Pop stack a la salida	3 4 2 *	+	/ y * tienen la misma precedencia
/	Push token al stack	3 4 2 *	/ +	/ tiene mayor precedencia que +
(	Push token al stack	3 4 2 *	( / +
1	agrega token a la salida	3 4 2 * 1	( / +
-	Push token al stack	3 4 2 * 1	- ( / +
5	agrega token a la salida	3 4 2 * 1 5	- ( / +
)	Pop stack a la salida	3 4 2 * 1 5 -	( / +	Repite hasta que sea encontrado "("
)	Pop stack	3 4 2 * 1 5 -	/ +	Descarta paréntesis emparejados
^	Push token al stack	3 4 2 * 1 5 -	^ / +	^ tiene mayor precedencia que /
2	agrega token a la salida	3 4 2 * 1 5 - 2	^ / +
^	Push token al stack	3 4 2 * 1 5 - 2	^ ^ / +	^ es evaluado de derecha a izquierda
3	agrega token a la salida	3 4 2 * 1 5 - 2 3	^ ^ / +
end	Pop todo el stack a la salida	3 4 2 * 1 5 - 2 3 ^ ^ / +

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.

Véase también

Enlaces externos

Java Applet demonstrating the Shunting yard algorithm
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

Datos: Q1199602