Algoritmo de patio de clasificación
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la
versión revisada el 3 de junio de 2021; las comprobaciones requieren
2 ediciones .
El algoritmo de la yarda de clasificación es una forma de analizar expresiones matemáticas y/o lógicas representadas en notación infija . Se puede utilizar para producir una notación polaca inversa o una salida de árbol de sintaxis abstracta . El algoritmo fue propuesto por Edsger Dijkstra y lo denominó "algoritmo del patio de maniobras", ya que se asemeja al funcionamiento de un patio de maniobras ferroviario .
Al igual que calcular los valores de las expresiones en notación polaca inversa, el algoritmo funciona mediante una pila . La notación infija de expresiones matemáticas es la más utilizada por las personas, sus ejemplos son 2+4 y 3+6*(3-2). Para convertir a notación polaca inversa, se utilizan 2 cadenas: entrada y salida, y una pila para almacenar declaraciones que aún no se agregaron a la cola de salida. Al convertir, el algoritmo lee 1 carácter y realiza acciones en función de este carácter.
Algoritmo
- Hasta que se procesen todos los tokens:
- Ficha de lectura .
- Si el token es un número , agréguelo a la cola de salida.
- Si el token es una función , entonces empújelo a la pila.
- Si el token es un separador de argumentos de función (por ejemplo, una coma):
- Siempre que el token en la parte superior de la pila no sea un paréntesis abierto:
- Empuje la declaración de la pila a la cola de salida.
- Si la pila termina antes de que se encuentre el token de llave de apertura , el separador de argumentos de función (coma) se omite de la expresión o se omite la llave de apertura .
- Si el token es un operador op1 , entonces:
- Siempre que haya un operador de token op2 en la parte superior de la pila, cuya precedencia sea mayor o igual que la de op1, y si las prioridades son iguales, op1 se deja asociativo :
- Empuje op2 de la pila a la cola de salida;
- Empuje op1 en la pila.
- Si el token es un paréntesis abierto , entonces empújelo a la pila.
- Si el token es una llave de cierre :
- Siempre que el token en la parte superior de la pila no sea un paréntesis abierto
- Empuje la declaración de la pila a la cola de salida.
- Si la pila termina antes de que se encuentre el token de paréntesis de apertura , entonces falta el paréntesis en la expresión.
- Extraiga el paréntesis abierto de la pila, pero no lo agregue a la cola de salida.
- Si el token en la parte superior de la pila es una función, empújelo a la cola de salida.
- Si no quedan más fichas en la entrada:
- Siempre que haya fichas de operador en la pila:
- Si el token del operador en la parte superior de la pila es un paréntesis abierto , entonces falta el paréntesis en la expresión.
- Empuje la declaración de la pila a la cola de salida.
Cada token-número, función u operador se imprime solo una vez, y cada token-función, operador o paréntesis se agregará y eliminará de la pila una vez. Número constante de operaciones por token, complejidad lineal del algoritmo O( n ).
Enlaces