ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Algoritmo shunting yard wiki: info, historia y vídeos

videos internet

salud  Algoritmo shunting yard 


El algoritmo shunting yard es un procedimiento para examinar (parsing) las ecuaciones matemáticas concretadas en la notación de infijo. Puede ser empleado para generar la salida en la notación polaca inversa (RPN) o bien como árbol de sintaxis abstracta (AST). El algoritmo fue inventado por Edsger Dijkstra y nombró como algoritmo "shunting yard" (patio de clasificación) pues su operación se semeja al de un patio de clasificación del tren.


Como la evaluación del RPN, el algoritmo shunting yard está basado en el stack. Las expresiones de infijo son la manera de matemáticas a la que la mayor parte de la gente está habituada, por servirnos de un ejemplo 3+4 o 3+4*(dos-1). Para la conversión hay 2 variables de texto (strings), la entrada y la salida. Hay asimismo un stack que guarda los operadores que aún 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 utilizando un cruce de tren de 3 vías. La entrada es procesada un símbolo al unísono, si es encontrada una variable o bien un número, es de forma directa copiado al salir b), d), f), h). Si el símbolo es un operador, es puesto en el stack (push) c), y también), no obstante, si su precedencia es menor que la del operador en el máximo del stack o bien las precedencias son iguales y el operador es asociativo por la izquierda, entonces aquel operador es sacado del stack (pop) y añadido al salir g). Por último, los operadores sobrantes son sacados del stack (pop) y agregados al salir.

Entrada: 3+4



  1. Agregue tres a la cola de salida (siempre y cuando un número es leído es agregado al salir)
  2. Empuje (push) el operador + (o bien su ID) sobre el stack de operadores
  3. Agregue cuatro a la cola de salida
  4. Después de acabar de leer la expresión, retire (pop) todos y cada uno de los operadores que se hallen en el stack y agréguelos al salir (en un caso así solo hay uno, "+")

Salida: tres cuatro +


Esto muestra ya dos reglas:



  • Todos los números son agregados al salir al instante en que son leídos.
  • Al final de la lectura de la expresión, se retira del stack (pop) a todos y cada uno de los operadores que hubiesen 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 razonamiento de función (ej., una coma):


  • Hasta que el token en el máximo 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 puesto mal o bien los paréntesis fueron mal emparejados.


  • Si el token es un operador, o1, entonces:


  • mientras que haya un operador, o2, en el máximo de la pila (esto excluye el paréntesis abierto), y
o1 es asociativo izquierdo y su precedencia es menor que (una precedencia más baja) o bien igual a la de o2, óo1 es asociativo derecho y su precedencia es menor que (una precedencia más baja) que la de o2,retire (pop) de la pila el o2, y póngalo en la cola de salida;

  • ponga (push) o1 en el máximo 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 máximo 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, mas no lo ponga en la cola de salida.
  • Si el token en el máximo de la pila es un token de función, póngalo (pop) en la cola de salida.
  • Si la pila se acaba sin localizar un paréntesis abierto, entonces hay paréntesis sin pareja.


  • Cuando no hay más tokens para leer:


  • Mientras aún haya tokens de operadores en la pila:


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

Para examinar la dificultad de tiempo de ejecución de este algoritmo, uno solo debe apreciar que cada token va a ser leído solo una vez, cada número, función, o bien operador va a ser impreso solo una vez, y cada función, operador o bien paréntesis va a ser puesto (push) en la pila y retirado (pop) de la pila solo una sola vez - por consiguiente, hay como máximo un número incesante de operaciones ejecutadas por token, y el tiempo de ejecución es de este modo O(n) - lineal al tamaño de la entrada.


Ejemplo detallado

Entrada: tres + cuatro * dos / ( 1 - cinco ) ^ dos ^ 3OperadorPrecedenciaAsociatividad^4de derecha a izquierda*3de izquierda a derecha/3de izquierda a derecha+2de izquierda a derecha-2de izquierda a derechaEntrada: tres + cuatro * dos / ( 1 - cinco ) ^ dos ^ 3TokenAcciónSalida (en RPN)Stack de operadoresNotas3agrega token a la salida3+Push token al stack3+4agrega token a la salida3 4+*Push token al stack3 4* +* tiene mayor precedencia que +2agrega token a la salida3 cuatro 2* +/Pop stack a la salida3 cuatro dos *+/ y * tienen exactamente la misma precedenciaPush token al stack3 cuatro dos */ +/ tiene mayor precedencia que +(Push token al stack3 cuatro dos *( / +1agrega token a la salida3 cuatro dos * 1( / +-Push token al stack3 cuatro dos * 1- ( / +5agrega token a la salida3 cuatro dos * 1 cinco- ( / +)Pop stack a la salida3 cuatro dos * 1 cinco -( / +Repite hasta el momento en que sea encontrado "("Pop stack3 cuatro dos * 1 cinco -/ +Descarta paréntesis emparejados^Push token al stack3 cuatro dos * 1 cinco -^ / +^ tiene mayor precedencia que /2agrega token a la salida3 cuatro dos * 1 cinco - 2^ / +^Push token al stack3 cuatro dos * 1 cinco - 2^ ^ / +^ es evaluado de derecha a izquierda3agrega token a la salida3 cuatro dos * 1 cinco - dos 3^ ^ / +endPop todo el stack a la salida3 cuatro dos * 1 cinco - dos tres ^ ^ / +

Si estuviese escribiendo un intérprete, esta salida sería tokenizada y escrita a un fichero compilado para ser interpretado más tarde.La conversión de infijo a RPN puede asimismo permitir una más simple simplificación de expresiones. Para hacer esto, actúe tal y como si estuviese resolviendo la expresión de RPN, no obstante, siempre y cuando llegue a una variable su valor es nulo, y toda vez que un operador tenga un valor nulo, y sus factores son escritos al salir (esto es una simplificación, los inconvenientes se presentan cuando los factores son operadores). En el momento en que un operador no tiene ningún factor nulo su valor sencillamente puede ser escrito al salir. Este procedimiento no incluye todas y cada una de las simplificaciones posibles; es más una optimización de plegamiento de incesante.


Véase también



  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Algoritmo shunting yard wiki: info, historia y vídeos

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas