Algoritme shunting yard

El algoritme shunting yard és un método per a analisar (parsing) les equacions matemàtiques especificades en la notació de infijo. En una forma senzilla d'entendre, si tens una equació matemàtica escrita de la forma tradicional, com "3 + 4 * (2 - 1)", l'algoritme "shunting yard" és com un organisador que pren eixa equació i la reordena per a que una computadora puga entendre-la i resoldre-la fàcilment (al final de l'algoritme tindria una eixida com esta: 3 4 2 * 1 5 - 2 ^ / +). Ho fa utilisant una espècie de "pila" per a guardar temporalment les operacions (com +, -, *, /) i després les organisa en un orde diferent, ya siga en un format cridat "notació polaca inversa" (RPN) o en una estructura d'arbre (arbre de sintaxis abstracta) que representa l'equació. l'algoritme va ser inventat per Edsger Dijkstra i va nomenar com a algoritme "shunting yard" (pati de classificació) perque la seua operació s'assembla al d'un pati de classificació del ferrocarril.

De la mateixa manera que la forma en que les calculadores evaluen les expressions en notació polaca inversa (RPN), l'algoritme 'shunting yard' utilisa una 'pila', que és com una torre a on pots apilar coses i solament pots traure la que està dalt. Les expressions en infijo, com '3 + 4' o '3 + 4 * (2 - 1)', són la forma en que la majoria de nosatres escrivim les equacions. Per a transformar estes equacions, l'algoritme utilisa dos 'caixes' de text: una per a l'equació original (l'entrada) i una atra per a l'equació reordenada (l'eixida). També té una 'pila' a on guarda temporalment els símbols d'operació (com +, -, *, /) abans de colocar-los en la 'caixa' d'eixida. L'algoritme llig cada símbol de l'equació un per un i decidix qué fer en ell.

Una conversió senzilla

Entrada: 3+4

1. Agregue 3 a la coa d'eixida (sempre que un número és llegit és agregat a l'eixida)
2. Espente (push) l'operador + (o el seu ID) sobre el stack d'operadors
3. Agregue 4 a la coa d'eixida
4. Despuix de terminar de llegir l'expressió, retire (pop) tots els operadors que es troben en el stack i agregue'ls a l'eixida (en este cas solament hi ha un, "+")

Eixida: 3 4 +

Açò mostra ya un parell de regles:

• Tots els números són agregats a l'eixida al moment en que són llegits.
• Al final de la llectura de l'expressió, es retira del stack (pop) a tots els operadors que hagueren i es posen en la coa d'eixida.

Per a analisar la complexitat de temps d'eixecució d'este algoritme, un solament té que notar que cada token serà llegit solament una volta, cada número, funció, o operador serà imprés solament una volta, i cada funció, operador o paréntesis serà posat (push) en la pila i retirat (pop) de la pila solament una sola volta - per lo tant, hi ha com a molt un número constant d'operacions eixecutades per token, i el temps d'eixecució és aixina O(n) - llineal al tamany de l'entrada.

Eixemple detallat

Archiu:Shunting yard.svg

Ilustració gràfica de l'algoritme usant un creuament de ferrocarril de tres vies. L'entrada és processada un símbol al mateix temps, si és trobada una variable o un número, és directament copiat a l'eixida b), d), f), h). Si el símbol és un operador, és colocat en el stack (push) c), i), no obstant, si la seua precedència és menor que la de l'operador en el top del stack o les precedència són iguals i l'operador és associatiu per l'esquerra, llavors aquell operador és tret del stack (pop) i afegitó a l'eixida g). Finalment, els operadors restants són trets del stack (pop) i agregats a l'eixida.

Entrada: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

Operador	Precedència	Asociatividad
^	4	de dreta a esquerra
*	3	d'esquerra a dreta
/	3	d'esquerra a dreta
+	2	d'esquerra a dreta
-	2	d'esquerra a dreta

Entrada: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

Token	Acció	Eixida (en RPN)	Stack d'operadors	Notes
3	agrega token a l'eixida	3
+	Push token al stack	3	+
4	agrega token a l'eixida	3 4	+
*	Push token al stack	3 4	* +	* té major precedència que +
2	agrega token a l'eixida	3 4 2	* +
/	Pop stack a l'eixida	3 4 2 *	+	/ i * tenen la mateixa precedència
	Push token al stack	3 4 2 *	/ +	/ té major precedència que +
(	Push token al stack	3 4 2 *	( / +
1	agrega token a l'eixida	3 4 2 * 1	( / +
-	Push token al stack	3 4 2 * 1	- ( / +
5	agrega token a l'eixida	3 4 2 * 1 5	- ( / +
)	Pop stack a l'eixida	3 4 2 * 1 5 -	( / +	Repetix fins que siga trobat "("
	Pop stack	3 4 2 * 1 5 -	/ +	Descarta paréntesis emparellats
^	Push token al stack	3 4 2 * 1 5 -	^ / +	^ té major precedència que /
2	agrega token a l'eixida	3 4 2 * 1 5 - 2	^ / +
^	Push token al stack	3 4 2 * 1 5 - 2	^ ^ / +	^ és evaluat de dreta a esquerra
3	agrega token a l'eixida	3 4 2 * 1 5 - 2 3	^ ^ / +
end	Pop tot el stack a l'eixida	3 4 2 * 1 5 - 2 3 ^ ^ / +

Si s'estiguera desenrollant un intérpret d'un llenguage de programació, l'eixida de l'algoritme "shunting yard" (ya siga en notació RPN o en un arbre de sintaxis abstracta) se sometria a un procés de tokenización i s'escriuria en un archiu compilado, llest per a la seua posterior eixecució. Adicionalment, la conversió d'expressions de infijo a RPN facilita la simplificació de dites expressions. Este procés de simplificació pot implementar-se simulant la resolució de l'expressió en RPN. No obstant, quan es troba una variable el valor de la qual és desconegut (nul), o quan un operador té un operant en valor nul, tant l'operador com els seus operants s'escriuen en l'eixida. És important destacar que este método representa una simplificació i pot presentar llimitacions quan els operants són, a la seua volta, operadors. En essència, esta tècnica constituïx una optimisació similar al plegament de constant, encara que no comprén totes les simplificació possibles

Vore també

• Parser de precedència d'operadors
• Notació polaca inversa
• Notació de infijo