Algoritmo polaca inversa

Estructuras de Datos Pilas Algoritmo: SUFIJO SIN PARENTESIS (Modificado para .NET). Dada una cadena de entrada (Entrada) representando una expresión infija cuyos símbolos de caracteres simples tienen valores de precedencia y rangos como se muestran en la tabla 1, una función string de nombre SIGCAR la cual cuando es invocada regresa el siguiente carácter en la expresión de entrada, un objeto Pila(Clase Stack). Este algoritmo convierte la cadena Entrada (infija) a su cadena polaca inversa equivalente Polaca. Rango contiene el valor de cada elemento de la cadena polaca inversa. Siguiente contiene el símbolo que se está examinando y sTemp es un objeto cadena temporal que contiene al elemento no apilado. Se asume que la cadena de entrada termina con el símbolo especial “#”. Entrada  Entrada+ “#” 1. Iniciar Pila (se asume que está vacía) Pila.Push(“#”) [Pila(Tope)  ‘#’ Iniciar la cadena de salida y el contador Rango: Polaca  ‘’ Rango  0 3. Obtener el primer símbolo de entrada: Siguiente  SIGCAR(Entrada) 4. Traducir la expresión infija: Repetir hasta el paso #6 Mientras Sigiente ≠ ‘’ Remover símbolos de la pila con precedencia mayor ó igual: Repetir Mientras f(Siguiente) ≤f(Pila(Tope) sTemp  Pila.Pop Polaca  Polaca + sTemp Rango  Rango + r(sTemp) If Rango < 1 Then Write (‘Inválida’) Exit 6. Apilar el símbolo actual y obtener el siguiente símbolo de entrada: Pila.Push(Siguiente) Siguiente  SIGCAR(Entrada) 7. Eliminar los elementos remanentes de la pila: Repetir Mientras la Pila no esté vacía: sTemp  Pila.Pop Polaca  Polaca + sTemp Rango  Rango + r(sTemp) If Rango <1 Then Write(‘Inválida’) Exit
1
1

2.

5.

J.P. Tremblay. An Introduction to Data Structures With Applications (p:204).

1

Ricardo A. Almanza Márquez

Estructuras de Datos Pilas

8.

¿Es válida la expresión? If Rango < 1 Then Write(‘Inválida’) Else Return Polaca

Ejemplo: a + b * c – d / e * h Salida: abc * + de / h * Tabla 1 Símbolo +, *. / a, b, c, .. Nulo (#) Precedencia(f) 1 2 3 0
2

Rango (r) -1 -1 1 _

Valores de corrida :
Símbolo Revisado a + b * c d / e * h # Contenido de la Pila (el símbolo más a la derecha es el tope) # #a #+ #+b #+* #+*c ##-d #-/ #-/e #-* #-*h # Polaca Inversa Rango

a a ab ab abc*+ abc*+ abc*+d abc*+d abc*+de/ abc*+de/ abc*+de/h*-

1 1 2 2 1 1 2 2 2 2 1

Aplicación: Polaca  abc*+de/h*Si los símbolos a – z representan númerosy si N1 y N2 son también números (que representan a los operandos de la expresión), entonces, la expresión polaca inversa es evaluada de la siguiente manera: Se lee de izquierda a derecha símbolo por símbolo: 1.- Si el símbolo es una letra (a – z) se apila: abc c b a

2

J. P. Tremblay p: 207.

2

Ricardo A. Almanza Márquez

Estructuras de Datos Pilas 2.- Si es un operador (+, -, *, /)se extraen dos operandos de la pila donde el primer elemento (tope) es N2 y el siguiente N2: N2  c y N1  b Se ejecuta la operación y el resultado se coloca en la pila. abc* Símbolo actual: * R  N1 * N2 R a

3.- Repetir desde el paso #1 hasta completar la lectura de la expresión polaca inversa. abc*+ Símbolo actual: + N2  R N1  a R  N1 + N2 R abc*+de e d R

abc*+de/ Símbolo: / N2  e, N1 d R’  N1 / N2 R’ R abc*+de/*h h R’ R

Símbolo: *

3

Ricardo A. Almanza Márquez

Estructuras de Datos Pilas N2  h’, N1  R’ R’  N1 * N2 R’ R Finalmente: abc*+de/h*Símbolo: N2  R’, N1  R R  N1 – N2 R Resultado Final.

Aplicación:

Donde:
txtExp Lower

btn1, btn2,…(Tag = 1, 2, …)

btnAdd: Tag = + btnSub: Tag = btnMult: Tag = * btnDiv: Tag = / btnOpenP: Tag = (

4Ricardo A. Almanza Márquez

Estructuras de Datos Pilas btnCloseP: Tag = ) btnPot: Tag = ^

labPolaca

labResult labCLS btnClearOne

Private Pila As New Stack Private sEntrada As String = "" Private Sub btn1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btn1.Click _ , btn2.Click, btn3.Click, btn4.Click, btn5.Click, btn6.Click, btn7.Click, btn8.Click, btn9.Click _...