Closed inrainmoi closed 8 months ago
Primero, hay que explicar una estructura de datos que será utilizada para los operadores que se van a aplicar sobre el mismo operando: una "Pila de Jerarquía".
Su notación posfija (sin incluir la asignación) es la siguiente:
En pseudocódigo, se generarán los siguientes temporales en ensamblador:
T0 = 5 * 6
T1 = T0 * 7
T2 = 8 * 9
T3 = T2 * 10
T4 = T3 + T1
T5 = T4
a = T5
Nótese que la última operación (T3 + T1) involucra temporales que no son consecutivos. Se necesita alguna forma de saber cuándo recordar el temporal T1, de modo que, cuando se encuentre el operador +, se aplique entre el último temporal utilizado (T3) y el temporal correspondiente (T1).
Ahora regresemos a la notación posfija (2), y revisemos la estructura de los temporales que están involucrados en la suma: T1 = 5 6 7 (3) T3 = 8 9 10 (4)
Consideremos que la multiplicación por 7 y 10 en ambos temporales son operaciones "encadenadas" con una secuencia de operaciones que se ejecutará completa, antes que otras. Es decir, Si tenemos: 8 10 3 / 5 / 7, la multiplicación por 10 y 3, y las divisiones entre 5 y 7, son operaciones "encadenadas" con la primera operación 8 * 10. Su notación posfija es: 8 10 3 5 / 7 /. Podemos notar que, al inicio de la secuencia, se tiene la estructura: Operando-Operando-Operador. Esto también está presente en la notación de los temporales T1 y T3 en (3) y (4). De modo que, cuando en una expresión se encuentre la estructura Operando-Operando-Operador, se recordará el último temporal utilizado.
Para saber cuándo encontramos el operador que se aplica a lo anterior, hay que reconocer otra estructura que podríamos encontrar en la misma expresión: Operando-Operador. Esta estructura simplemente se aplicará con el Operador y el último temporal utilizado (como 4 6 / 7 -> 4 6 7 /: 4 * 6 se guardará en T0, y al encontrar 7 /, T0 / 7 se guardará en T1). Sabiendo esto, cuando se encuentre la estructura: Operador, al no tener operandos cerca, el operador se está aplicando sobre los últimos dos temporales, siendo uno de ellos no necesariamente el penúltimo, como en el ejemplo (T3 + T1); en realidad, se está aplicando entre las últimas dos secuencias, como en (3) y (4). De modo que se asumirá que se aplica con el último temporal utilizado, y el último temporal recordado en la Pila de Jerarquía.
En el ejemplo, con el operador +, se aplicará entre el último temporal T3, y el último temporal en la Pila T1, que será "recordado" cuando se encuentre: 8 9 *.
Existe un caso especial: Cuando se encuentre solamente la estructura Operando. Por ejemplo: 10 + 5 8 -> 10 5 8 10 + Al inicio de la notación posfija, se observa que la estructura no coincide con Operando-Operando-Operador u Operando-Operador. Este caso es especial, porque la secuencia contiene solamente un elemento: el número 10. Esto es consistente con la idea de la Pila de Jerarquías, ya que, si se recuerda este número en la Pila de Jerarquías, al encontrar el operador +, se aplicará entre el último temporal (5 * 8) y 10. Al ser solamente un número, y no una operación aritmética, no se utiliza un temporal para recordarlo; por esta razón, el ensamblador se vería como sigue:
T0 = 5 * 8
T1 = T0 + 10
De esta manera, el número de temporales utilizados para esta expresión será consistente con los necesarios para dicha expresión: 1 para la multiplicación, otro para la suma, y por supuesto, otro para la asignación, ya que para todas las expresiones mencionadas se asumirá que se asignan a una variable.
Algoritmo:
$AuxTabla$ se coloca en el primer Nodo Mientras $AuxTabla$ no sea el punto y coma
Si la estructura del nodo actual y los dos siguientes es: $AuxTabla$ = Operando, $AuxTabla->siguiente$ = Operando, $AuxTabla->siguiente->siguiente$ = Operador
Si CasoEspecial Esta Activado
Se agrega el número anterior como si fuera un temporal en la pila de jerarquías Se desactiva CasoEspecial
Si no
Se recuerda en la Pila de Jerarquías el último temporal utilizado (Se agrega a la Pila)
Se utiliza un nuevo temporal para guardar el resultado de esta operacion (Operando Operador Operando) $T+1$ = ($AuxTabla$) ($AuxTabla->siguiente->siguiente$) ($AuxTabla->siguiente$) $AuxTabla$ avanza tres nodos
Sino, Si la estructura del nodo actual y el siguiente es: $AuxTabla$ = Operando, $AuxTabla->siguiente$ = Operador
Se utiliza un nuevo temporal para guardar el resultado de la operacion con el operando, el operador y el último temporal utilizado $T+1$ = ($T$) ($AuxTabla->siguiente$) ($AuxTabla$) $AuxTabla$ avanza dos nodos
Sino, Si la estructura del nodo actual es: $AuxTabla$ = Operador
Se utiliza un nuevo temporal para guardar el resultado de la operacion con el operando, el último temporal utilizado, y el temporal (o número, para el Caso Especial) al frente de la pila $T+1$ = ($T_PilaJerarquia$) ($AuxTabla$) ($T$) Se retira el temporal al frente de la pila $AuxTabla$ avanza un nodo
Sino, Si la estructura del nodo actual es: $AuxTabla$ = Operando [Caso Especial]
Se activa CasoEspecial
$AuxTabla$ avanza un nodo
Utilizando el algoritmo anterior, se muestra el resultado del ensamblador, en pseudocódigo, para cada expresión en notación posfija desarrollada en el comentario anterior:
10
CasoEspecial = Activado
5 8 *
AgregaPilaJerarquia(10)
CasoEspecial = Desactivado
T0 = 5 * 8
+
T1 = TopePilaJerarquia(10) + T0
RetiraPilaJerarquia(10)
Resultado:
T0 = 5 * 8
T1 = 10 + T0
6 7 *
T0 = 6 * 7
5 9 /
AgregaPilaJerarquia(T0)
T1 = 5 / 9
+
T2 = TopePilaJerarquia(T0) + T1
RetiraPilaJerarquia(T0)
Resultado:
T0 = 6 * 7
T1 = 5 / 9
T2 = T0 + T1
9
CasoEspecial = Activado
6 2 /
AgregaPilaJerarquia(9)
CasoEspecial = Desactivado
T0 = 6 / 2
-
T1 = TopePilaJerarquia(9) - T0
RetiraPilaJerarquia(9)
7 +
T2 = T1 + 7
Resultado:
T0 = 6 / 2
T1 = TopePilaJerarquia(9) - T0
T2 = T1 + 7
9
CasoEspecial = Activado
5 2 /
AgregaPilaJerarquia(9)
CasoEspecial = Desactivado
T0 = 5 / 2
8 *
T1 = T0 * 8
4 *
T2 = T1 * 4
5 /
T3 = T2 / 5
-
T4 = TopePilaJerarquia(9) - T3
RetiraPilaJerarquia(9)
7 +
T5 = T4 + 7
6 -
T6 = T5 - 6
Resultado:
T0 = 5 / 2
T1 = T0 * 8
T2 = T1 * 4
T3 = T2 / 5
T4 = TopePilaJerarquia(9) - T3
T5 = T4 + 7
T6 = T5 - 6
8
CasoEspecial = Activado
3 5 *
AgregaPilaJerarquia(8)
CasoEspecial = Desactivado
T0 = 3 * 5
2 /
T1 = T0 / 2
-
T2 = TopePilaJerarquia(8) - T1
RetiraPilaJerarquia(8)
9 1 *
AgregaPilaJerarquia(T2)
T3 = 9 * 1
3 /
T4 = T3 / 3
+
T5 = TopePilaJerarquia(T2) + T4
5 +
T6 = T5 + 5
Resultado:
T0 = 3 * 5
T1 = T0 / 2
T2 = TopePilaJerarquia(8) - T1
T3 = 9 * 1
T4 = T3 / 3
T5 = TopePilaJerarquia(T2) + T4
T6 = T5 + 5
Propongo un algoritmo y algunos casos de prueba, para desarrollar la idea de la conversión a la notación posfija.
Se asume que todas las expresiones de los casos de prueba serán asignadas a una variable, y que la asignación será el último operador, tanto en la notación posfija, como en el ensamblador
El algoritmo propuesto es el siguiente. Los invito a realizar pruebas de escritorio con él:
Algoritmo:
- El indice AuxTabla se coloca en el primer operador
- El primer operando a la izquierda de la expresion se coloca en la lista Posfija
- Mientras AuxTabla no llegue al punto y coma
- ¿El operador evaluado es una multiplicación o división? Si
- Se agrega el primer operando a la izquierda del operador a la notacion posfija.
- Mientras los operadores sean multiplicaciones o divisiones
- Agrega el operador y el siguiente operando a la pila MulDiv (cuando se extraegan, por el principio LIFO, quedarán en notación posfija)
- Mientras la Pila MulDiv no se vacie
- Extrae los tokens metidos a la pila MulDiv desde la izquierda, para que se respete que los operandos con la misma precedencia se ejecuten de izquierda a derecha, y colocalos en la lista Posfija
- Si no ¿El operador evaluado es una suma o resta? Si
- ¿El siguiente operador es una multiplicacion o division? Si
- Se agrega el primer operando despues de la suma a la notacion posfija.
- Mientras los operadores sean multiplicaciones o divisiones
- Agrega el operador y el siguiente operando a la pila MulDiv (cuando se extraegan, por el principio LIFO, quedarán en notación posfija)
- Mientras la Pila MulDiv no se vacie
- Extrae los tokens metidos a la pila MulDiv desde la izquierda, para que se respete que los operandos con la misma precedencia se ejecuten de izquierda a derecha, y colocalos en la lista Posfija
- Extrae el ultimo operador metido a la pila SumRes
- Si no ¿El siguiente operador es una suma o resta? Si
- Mientras el siguiente operador no sea multiplicacion o division
- Agrega el operador y el siguiente operando a la pila SumRes (cuando se extraegan, por el principio LIFO, quedarán en notación posfija)
- Mientras la pila SumRes no se vacíe
- Extrae los tokens metidos a la pila SumRes desde la izquierda, para que se respete que los operandos con la misma precedencia se ejecuten de izquierda a derecha, y colocalos en la lista Posfija
- AuxTabla pasa al siguiente token, para procesar la siguiente instruccion
Aquí algunos casos de prueba:
*10 + 5 8**
Posfija Generada: 10 5 8 * + Con el algoritmo anterior, las pilas y el desarrollo de la notacion posfija se ven, en cada paso, de la siguiente manera:
PilaMulDiv: PilaSumRes: Posfija: 10 PilaMulDiv: PilaSumRes: + Posfija: 10 PilaMulDiv: PilaSumRes: + Posfija: 10 5 PilaMulDiv: * 8 PilaSumRes: + Posfija: 10 5 PilaMulDiv: PilaSumRes: + Posfija: 10 5 8 * PilaMulDiv: PilaSumRes: Posfija: 10 5 8 * +
*6 7 + 5 / 9**
Posfija Generada: 6 7 * 5 9 / + Con el algoritmo anterior, las pilas y el desarrollo de la notacion posfija se ven, en cada paso, de la siguiente manera:
PilaMulDiv: PilaSumRes: Posfija: 6 PilaMulDiv: * 7 PilaSumRes: Posfija: 6 PilaMulDiv: PilaSumRes: Posfija: 6 7 * PilaMulDiv: PilaSumRes: + Posfija: 6 7 * PilaMulDiv: PilaSumRes: + Posfija: 6 7 * 5 PilaMulDiv: / 9 PilaSumRes: + Posfija: 6 7 * 5 PilaMulDiv: PilaSumRes: + Posfija: 6 7 * 5 9 / PilaMulDiv: PilaSumRes: Posfija: 6 7 * 5 9 / +
9 + 7 - 6 / 2
Posfija Generada: 9 6 2 / - 7 + Con el algoritmo anterior, las pilas y el desarrollo de la notacion posfija se ven, en cada paso, de la siguiente manera:
PilaMulDiv: PilaSumRes: Posfija: 9 PilaMulDiv: PilaSumRes: + 7 Posfija: 9 PilaMulDiv: PilaSumRes: + 7 - Posfija: 9 PilaMulDiv: PilaSumRes: + 7 - Posfija: 9 6 PilaMulDiv: / 2 PilaSumRes: + 7 - Posfija: 9 6 PilaMulDiv: PilaSumRes: + 7 - Posfija: 9 6 2 / PilaMulDiv: PilaSumRes: + 7 Posfija: 9 6 2 / - PilaMulDiv: PilaSumRes: Posfija: 9 6 2 / - 7 +
9 + 7 - 6 - 5 / 2 8 4 / 5;
Posfija Generada: 9 5 2 / 8 4 5 / - 7 + 6 - Con el algoritmo anterior, las pilas y el desarrollo de la notacion posfija se ven, en cada paso, de la siguiente manera:
PilaMulDiv: PilaSumRes: Posfija: 9 PilaMulDiv: PilaSumRes: + 7 Posfija: 9 PilaMulDiv: PilaSumRes: + 7 - 6 Posfija: 9 PilaMulDiv: PilaSumRes: + 7 - 6 - Posfija: 9 PilaMulDiv: PilaSumRes: + 7 - 6 - Posfija: 9 5 PilaMulDiv: / 2 PilaSumRes: + 7 - 6 - Posfija: 9 5 PilaMulDiv: / 2 * 8 PilaSumRes: + 7 - 6 - Posfija: 9 5 PilaMulDiv: / 2 * 8 * 4 PilaSumRes: + 7 - 6 - Posfija: 9 5 PilaMulDiv: / 2 * 8 * 4 / 5 PilaSumRes: + 7 - 6 - Posfija: 9 5 PilaMulDiv: * 8 * 4 / 5 PilaSumRes: + 7 - 6 - Posfija: 9 5 2 / PilaMulDiv: * 4 / 5 PilaSumRes: + 7 - 6 - Posfija: 9 5 2 / 8 * PilaMulDiv: / 5 PilaSumRes: + 7 - 6 - Posfija: 9 5 2 / 8 * 4 * PilaMulDiv: PilaSumRes: + 7 - 6 - Posfija: 9 5 2 / 8 * 4 * 5 / PilaMulDiv: PilaSumRes: + 7 - 6 Posfija: 9 5 2 / 8 * 4 * 5 / - PilaMulDiv: PilaSumRes: - 6 Posfija: 9 5 2 / 8 * 4 * 5 / - 7 + PilaMulDiv: PilaSumRes: Posfija: 9 5 2 / 8 * 4 * 5 / - 7 + 6 -
8 + 5 - 3 5 / 2 + 9 1 / 3;
Posfija Generada: 8 3 5 2 / - 9 1 3 / + 5 + Con el algoritmo anterior, las pilas y el desarrollo de la notacion posfija se ven, en cada paso, de la siguiente manera:
PilaMulDiv: PilaSumRes: Posfija: 8 PilaMulDiv: PilaSumRes: + 5 Posfija: 8 PilaMulDiv: PilaSumRes: + 5 - Posfija: 8 PilaMulDiv: PilaSumRes: + 5 - Posfija: 8 3 PilaMulDiv: * 5 / 2 PilaSumRes: + 5 - Posfija: 8 3 PilaMulDiv: PilaSumRes: + 5 - Posfija: 8 3 5 * 2 / PilaMulDiv: PilaSumRes: + 5 Posfija: 8 3 5 * 2 / - PilaMulDiv: PilaSumRes: + 5 + Posfija: 8 3 5 * 2 / - PilaMulDiv: PilaSumRes: + 5 + Posfija: 8 3 5 * 2 / - 9 PilaMulDiv: * 1 / 3 PilaSumRes: + 5 + Posfija: 8 3 5 * 2 / - 9 PilaMulDiv: PilaSumRes: + 5 + Posfija: 8 3 5 * 2 / - 9 1 * 3 / PilaMulDiv: PilaSumRes: + 5 Posfija: 8 3 5 * 2 / - 9 1 * 3 / + PilaMulDiv: PilaSumRes: Posfija: 8 3 5 * 2 / - 9 1 * 3 / + 5 +
Encontré un algoritmo llamado "shunting yard" para convertir las expresiones a notación posfija que solo utiliza dos pilas, una para la salida y otra para los operadores y además considera paréntesis. A primera vista me parece un algoritmo un poco más sencillo que el que propusiste, ¿que te parece?
@inrainmoi De hecho también lo encontré, optimiza la parte de multiplicar dentro de la suma
Me parece muy bien
Propongo un algoritmo y algunos casos de prueba, para desarrollar la idea de la conversión a la notación posfija.
Se asume que todas las expresiones de los casos de prueba serán asignadas a una variable, y que la asignación será el último operador, tanto en la notación posfija, como en el ensamblador
El algoritmo propuesto es el siguiente. Los invito a realizar pruebas de escritorio con él:
Algoritmo:
Aquí algunos casos de prueba:
*10 + 5 8**
Posfija Generada: 10 5 8 * + Con el algoritmo anterior, las pilas y el desarrollo de la notacion posfija se ven, en cada paso, de la siguiente manera:
*6 7 + 5 / 9**
Posfija Generada: 6 7 * 5 9 / + Con el algoritmo anterior, las pilas y el desarrollo de la notacion posfija se ven, en cada paso, de la siguiente manera:
9 + 7 - 6 / 2
Posfija Generada: 9 6 2 / - 7 + Con el algoritmo anterior, las pilas y el desarrollo de la notacion posfija se ven, en cada paso, de la siguiente manera:
9 + 7 - 6 - 5 / 2 8 4 / 5;
Posfija Generada: 9 5 2 / 8 4 5 / - 7 + 6 - Con el algoritmo anterior, las pilas y el desarrollo de la notacion posfija se ven, en cada paso, de la siguiente manera:
8 + 5 - 3 5 / 2 + 9 1 / 3;
Posfija Generada: 8 3 5 2 / - 9 1 3 / + 5 + Con el algoritmo anterior, las pilas y el desarrollo de la notacion posfija se ven, en cada paso, de la siguiente manera: