Especificaciones de Estructura de datos - Pila PDF

Preview

Summary

Resumen Estructura de datos - Pila...

Description

1

Traducción de una expresión en un árbol binario En este apartado se describen algunos algoritmos que permiten obtener la representación en árbol binario de una expresión matemática partiendo de la lista de términos que la componen expresados en la notación habitual (notación infija). El tipo de expresiones que pueden traducir estos algoritmos está limitado a las condiciones expuestas en la práctica del curso, en el último apartado se exponen algunas técnicas para que puedan tratar expresiones más complejas. 1. Introducción Para nuestro problema una expresión matemática será un medio que permite indicar el orden en que se deben realizar una serie de operaciones para obtener un resultado. Las operaciones se indican mediante operadores, que en nuestro caso representan las operaciones sumas, resta, producto, división e igualdad, todas ellas operaciones binarias (necesitan exactamente dos argumentos para poderse evaluar). Existen varias notaciones para representar expresiones matemáticas, que se diferencian en el orden en que se escriben los argumentos (operando) de los operadores. Las más relevantes son: • • • •

Notación infija: La notación habitual. El orden es primer operando, operador, segundo operando. Notación prefija: El orden es operador, primer operando, segundo operando. Notación postfija: El orden es primer operando, segundo operando, operador. Notación funcional: Se escribe el operador/función y después, entre paréntesis, los operadores separados por comas.

La notación infija tiene el problema de que en expresiones con más de un operador existe ambigüedad sobre cual es el orden de evaluación. Por ejemplo, la expresión 8/4/2 se puede interpretar como (8 / 4) /2 o bien como 8 / (4 / 2). Las otras notaciones no sufren este problema. Para resolver estas ambigüedades, se añaden unas reglas denominadas orden de precedencia de operadores. Cuando dos operadores compiten por el mismo operando (en el ejemplo anterior, el primer y el segundo operador de división se disputan el operando 4) gana el operador (se evalúa primero) con mayor precedencia, o a igualdad de precedencia, el operador situado más a la izquierda. Las reglas de precedencia habituales son que los operadores división y producto tienen igual precedencia y ganan al resto de operadores, y que los operadores suman y resta tienen igual precedencia y ganan al operador igualdad. Así, la expresión 8/4/2 se evalúa como (8 / 4) / 2, y 2+3*4 se evalúa como 2+(3*4). Si deseamos cambiar el orden de evaluación, se pueden agrupar partes de una expresión utilizando paréntesis.

1

IS310 – Algoritmos y Estructuras de Datos – INGENIERÍA EN SISTEMAS I PAC 2020

2

En el resto de las notaciones no es necesario utilizar paréntesis ya que siempre podemos indicar el orden exacto de evaluación sin que exista ambigüedad. Por ejemplo, si deseamos representar las expresiones (2+(3*4)) = x y ((2+3)*4)= x en las cuatro notaciones mencionadas, el resultado sería: (2+(3*4)) = x

((2+3)*4) = x

Notación prefija

=+2*34x

=*+234x

Notación infija

2+3*4 = x

(2+3)*4 = x

Notación postfija

234*+x=

23+4*x=

Notación funcional igual(suma(2,producto(3,4)),x)

igual(producto(suma(2,3),4),x)

Generalmente a la hora de traducir una expresión en notación infija a su representación como árbol binario se suele efectuar un primer paso de traducción a una notación más adecuada (generalmente a notación prefija o postfija), y luego se traduce la expresión en esa notación a árbol binario. Las dos etapas anteriores se pueden realizar directamente mediante un algoritmo recursivo, o en dos pasos utilizando estructuras adicionales (generalmente pilas). 2. Algoritmo recursivo Es posible traducir directamente una expresión en notación infija a un árbol binario mediante uno o varios subprogramas recursivos, aunque el algoritmo no es trivial. En lugar de intentar desarrollar un único subprograma que analice completamente una expresión, suele ser más sencillo utilizar un enfoque ligeramente distinto, utilizando dos subprogramas: •

•

•

2

El primero de ellos se encargaría de asignar el operando derecho a un operador, el cual se proporciona como un árbol binario al que le falta el hijo derecho, utilizando para ello la lista de términos correspondiente a la parte de la expresión que falta por traducir. El resultado del subprograma será el árbol binario completado y la lista de términos que faltan por analizar. El segundo subprograma traduce parte o toda una expresión en un árbol binario, que pasa a considerarse como operando. Una expresión en notación infija responde al esquema N1 O1 N2O2 N3..., donde los términos Ni son operando y los términos Oi operadores. Este subprograma construiría el árbol binario asignando N1 como operando izquierdo de O1, y llamaría al subprograma anterior para encontrar el operando derecho de O1. Por ejemplo, en la expresión 2*3+4, el operando derecho del producto es 3, pero en la expresión 2+3*4 el operando derecho de la suma es el árbol binario (3*4). Si en algún momento aparece un paréntesis izquierdo en lugar de un operando, se llamaría al segundo subprograma para que traduzca esa subexpresión al árbol binario correspondiente, que pasa a considerarse como el operando que faltaba.

IS310 – Algoritmos y Estructuras de Datos – INGENIERÍA EN SISTEMAS I PAC 2020

3

3. Conversión de notación infija a postfija El siguiente algoritmo en pseudocódigo traduce una expresión en notación infija a notación postfija, como paso previo a la obtención del árbol binario correspondiente a la expresión: • • •

Entrada: Una lista que contiene los términos de la ecuación en notación infija (la notación habitual). Salida: Una lista que contiene los términos de la ecuación en notación postfija. Datos locales: Una pila, que va a contener operadores y paréntesis izquierdos.

INICIO Crear pila y la lista de salida, inicialmente vacías. MIENTRAS lista de entrada no este vacía y no se ha encontrado ningún error HACER Extraer el primer termino de la lista (lo llamaremos E) SEGUN-SEA E CASO E es número: Insertar E al final de la lista de salida CASO E es la variable x: Insertar E al final de la lista de salida CASO E es un paréntesis izquierdo: Insertar E en la pila CASO E es un paréntesis derecho: MIENTRAS La pila no este vacía y su cima no sea un paréntesis izquierdo HACER Extraer elemento de la pila Insertarlo al final de la lista de salida FIN-MIENTRAS SI Encontramos el paréntesis izquierdo ENTONCES Extraerlo de la pila y destruirlo SINO Se ha detectado un ERROR 2 FIN-SI Destruir E CASO E es un operador: MIENTRAS La pila no este vacía y su cima sea un operador de precedencia mayor o igual que la de E HACER Extraer elemento de la pila Insertarlo al final de la lista de salida FIN-MIENTRAS Insertar E en la pila FIN-SEGUN-SEA FIN-MIENTRAS MIENTRAS Pila no esté vacía HACER

3

IS310 – Algoritmos y Estructuras de Datos – INGENIERÍA EN SISTEMAS I PAC 2020

4

Extraer elemento de la pila Insertarlo al final de la lista de salida FIN-MIENTRAS Destruir pila FIN A continuación, se muestra el estado de la lista de entrada, la lista de salida y la pila en cada iteración del bucle principal del algoritmo al dar como entrada la lista de términos correspondiente al ejemplo del enunciado de la práctica. En color rojo se muestra el término que se procesa en cada iteración, y en color verde los términos que se han añadido a la lista de salida o a la pila como consecuencia de las acciones realizadas en la iteración anterior: -4 * ( -5 - 2 ) / ( -1 * x - -3 ) = -1 / -2 * ( -5 - 2 ) / ( -1 * x - -3 ) = -1 / -2

-4

( -5 - 2 ) / ( -1 * x - -3 ) = -1 / -2

-4

-5 - 2 ) / ( -1 * x - -3 ) = -1 / -2 - 2 ) / ( -1 * x - -3 ) = -1 / -2 2 ) / ( -1 * x - -3 ) = -1 / -2 ) / ( -1 * x - -3 ) = -1 / -2

*

-4

(*

-4 -5

(*

-4 -5

-( *

-4 -5 2

-( *

/ ( -1 * x - -3 ) = -1 / -2

-4 -5 2 -

*

( -1 * x - -3 ) = -1 / -2

-4 -5 2 - *

/

-1 * x - -3 ) = -1 / -2 * x - -3 ) = -1 / -2 x - -3 ) = -1 / -2

-4 -5 2 - *

(/

-4 -5 2 - * -1

(/

-4 -5 2 - * -1

*(/

- -3 ) = -1 / -2

-4 -5 2 - * -1 x

*(/

-3 ) = -1 / -2

-4 -5 2 - * -1 x *

-(/

-4 -5 2 - * -1 x * -3

-(/

) = -1 / -2 = -1 / -2 -1 / -2 / -2 -2

4

-4 -5 2 - * -1 x * -3 -

/

-4 -5 2 - * -1 x * -3 - /

=

-4 -5 2 - * -1 x * -3 - / -1

=

-4 -5 2 - * -1 x * -3 - / -1

/=

IS310 – Algoritmos y Estructuras de Datos – INGENIERÍA EN SISTEMAS I PAC 2020

5

-4 -5 2 - * -1 x * -3 - / -1 -2

/=

-4 -5 2 - * -1 x * -3 - / -1 -2 / = Nota: El algoritmo anterior no puede detectar errores relacionados con la ausencia de paréntesis de cierre. Aunque con una pequeña modificación es posible detectarlos, se ha preferido hacerlo en la siguiente etapa: 4. Traducción de notación postfija a árbol binario • • •

Entrada: La lista obtenida en el algoritmo anterior, que contiene los términos de la ecuación en notación postfija. Salida: Un árbol binario que representa la ecuación. Datos locales: Una pila, que va a contener operando (números, la variable x y expresiones (subárboles).

INICIO Crear pila y árbol, inicialmente vacíos. MIENTRAS lista de entrada no este vacía y no se ha encontrado ningún error HACER Extraer el primer termino de la lista (lo llamaremos E) SEGUN-SEA E CASO E es número: Insertar E en la pila CASO E es la variable x: Insertar E en la pila CASO E es una expresión (un árbol): Insertar E en la pila CASO E es un paréntesis izquierdo: Se ha detectado un ERROR 2 CASO E es un operador: SI La pila tiene menos de dos elementos ENTONCES Se ha detectado un ERROR 3 SINO Extraer elemento de la pila (lo llamaremos A2) Extraer elemento de la pila (lo llamaremos A1) Crear un árbol donde la raíz contenga al operador E, el hijo izquierdo sea A1 y el hijo derecho sea A2 Insertar el árbol en la pila FIN-SI FIN-SEGUN-SEA FIN-MIENTRAS SI pila vacía o con más de un elemento ENTONCES Se ha detectado un ERROR 3

5

IS310 – Algoritmos y Estructuras de Datos – INGENIERÍA EN SISTEMAS I PAC 2020

6

SINO Extraer elemento de la pila (lo llamaremos E) SI Elemento no es una expresión (un árbol) ENTONCES Convertir E en un árbol con hijo izquierdo y derecho vacíos FIN-SI El resultado del algoritmo (el árbol de salida) es E FIN-SI {Borrado de la pila, si se ha producido error} MIENTRAS pila no esté vacía HACER Extraer elemento de la pila Destruir elemento FIN-MIENTRAS Destruir pila FIN A continuación, se muestra el estado de la lista de entrada y la pila al ejecutar el algoritmo anterior sobre la lista de términos en notación postfija obtenidos anteriormente. Para abreviar el listado, cuando varios términos consecutivos de la lista son operando se han agrupado las iteraciones correspondientes en una única línea: -4 -5 2 - * -1 x * -3 - / -1 -2 / = - * -1 x * -3 - / -1 -2 / = * -1 x * -3 - / -1 -2 / =

2 -5 -4 -4

-1 x * -3 - / -1 -2 / =

* -3 - / -1 -2 / =

x -1

-3 - / -1 -2 / =

6

IS310 – Algoritmos y Estructuras de Datos – INGENIERÍA EN SISTEMAS I PAC 2020

7

- / -1 -2 / =

-3

/ -1 -2 / =

-1 -2 / =

/=

-2 -1

=

El resultado es el árbol binario resultante de extraer el único termino existente en la pila.

7

IS310 – Algoritmos y Estructuras de Datos – INGENIERÍA EN SISTEMAS I PAC 2020

8

5. Traducción de expresiones más complejas Aunque no es necesario para la realización de la práctica, se ha incluido este apartado para aquellos que deseen saber cómo ampliar los algoritmos anteriores para el tratamiento de expresiones más complejas, que incluyan variables, excepciones a la regla de precedencia, operadores unarios y funciones. •

Variables: En los ejemplos anteriores sólo estaba permitido utilizar una variable, denominada x. Si se desea utilizar cualquier número de variables con otros nombres, lo único que se necesita es adaptar la definición del término de tipo variable para que almacene una cadena de caracteres correspondiente a su nombre. No es necesario cambiar ninguno de los algoritmos anteriores.

•

Excepciones a las reglas de precedencia: Los operadores potencia y asignación presentan excepciones a la regla de precedencia. Cuando el operador potencia compite con otro operador potencia por un operando, gana el operador situado más a la derecha en la expresión, al contrario de lo habitual. Por ejemplo, la expresión 2^3^4 se interpreta como 2^(3^4). El operador asignación (Nota: Nos referimos al operador matemático, no al operador de Pascal) tiene definida la mayor precedencia posible respecto a los operandos que estén a su izquierda, y la menor precedencia posible respecto a los que estén a su derecha. Por ejemplo, la expresión a+b...