.
Enunciado
Desarrollar un programa que implemente una Calculadora RPN (Notación Polaca Inversa).
Análisis
La Notación Polaca Inversa (o RPN – “Reverse Polish Notation”) es alternativa a la notación algebraica tradicional y tiene la gran ventaja de no requerir el uso de paréntesis para indicar precedencia en las operaciones parciales de la expresión.
Por ejemplo en la notación algebraica tradicional, para resolver la siguiente expresión:
( 4 + 2 ) * ( 5 – 2 )
se debe resolver primero ( 4 + 2 ), luego ( 5 – 2 ) y luego multiplicar los dos resultados parciales (que en este caso son 6 y 3):
( 4 + 2 ) * ( 5 – 2 )
6 * 3
18
6 * 3
18
Si utilizamos RPN, la expresión anterior será:
4 2 + 5 2 - *
y debe interpretarse como una pila de operandos. Es decir: debemos leer la expresión RPN de izquierda a derecha y analizar cada componente para determinar si se trata de un operando o de un operador. Si el componente es un operando entonces lo apilamos. Si es un operador entonces sacamos dos operandos de la pila, los operamos entre si y apilamos el resultado.
Leyendo cada componente de la expresión anterior veremos a continuación como queda la pila de operandos:
El gráfico muestra como los datos se introducen "desde abajo" de forma tal que "empujan hacia arriba" a los datos que ya existen. Al ingresar un operador toma los dos primeros datos de la pila (los dos de más abajo), los opera e introduce el resultado en la pila.
Veamos el programa principal.
El usuario ingresa una expresión por teclado. Puede ingresar un valor numérico o un operador. Para salir del programa debe ingresar la palabra "FIN".
Lo primero que tenemos que determinar es si el usuario ingresó un operando (un número) o un operador (una operación). La forma de saberlo será preguntando si la expresión ingresada es '+', '-', '*' o '/'. Si es alguna de estas cadenas entonces se trata de un operador, si no se trata de un operando ya que no vamos a considerar la posibilidad de que existan errores.
Para no "ensuciar" el programa con un if lleno de ANDs desarrollamos la función esOperador que retorna true si la expresión es numérica o false si no lo es.
Como vemos, la función esOperador recibe un string y pregunta si es distinto de todos los operadores conocidos. Si esto es así entonces asume que se trata de un operador.
Volviendo al programa principal, una vez ingresada la primer expresión (dentro del while) invocamos a la función esOperadorfin para saber que hacer.
Si el usuario ingresó un operando (un número) entonces lo apilamos en la pila apuntada por p.
Notemos que el operando ingresado está dentro de la variable exp que es de tipo string. Así que antes de poderlo apilar debemos convertirlo a real (es decir convertirlo a un tipo numérico).
Si el usuario ingresó un operador entonces (entrando por el lado derecho del if) tenemos que sacar dos elementos de la pila, operarlos entre si con el operador ingresado por el usuario, apilar el resultado y mostrar el contenido de la pila que, en definitiva, será el resultado de la operación.
Hasta aquí sabemos que debemos efectuar una operación, pero no sabemos cual. Tenemos que preguntar cual es el operador contenido en la variable exp y aplicar la operación que corresponda.
Otra vez, para no "ensuciar" el programa con "ifes" desprolijos utilizamos la función operar que recibe los dos operandos (v1 y v2) y el operador a aplicar (contenido en exp).
Volviendo al programa principal, una vez ingresada la primer expresión (dentro del while) invocamos a la función esOperadorfin para saber que hacer.
Si el usuario ingresó un operando (un número) entonces lo apilamos en la pila apuntada por p.
Notemos que el operando ingresado está dentro de la variable exp que es de tipo string. Así que antes de poderlo apilar debemos convertirlo a real (es decir convertirlo a un tipo numérico).
Si el usuario ingresó un operador entonces (entrando por el lado derecho del if) tenemos que sacar dos elementos de la pila, operarlos entre si con el operador ingresado por el usuario, apilar el resultado y mostrar el contenido de la pila que, en definitiva, será el resultado de la operación.
Hasta aquí sabemos que debemos efectuar una operación, pero no sabemos cual. Tenemos que preguntar cual es el operador contenido en la variable exp y aplicar la operación que corresponda.
Otra vez, para no "ensuciar" el programa con "ifes" desprolijos utilizamos la función operar que recibe los dos operandos (v1 y v2) y el operador a aplicar (contenido en exp).
Para mostrar la pila utilizamos una especie de "pila auxiliar" que será la que en realidad vamos a mostrar. La idea es recorrer la pila apilando cada elemento en otra pila de forma tal que la pila auxiliar tendrá un orden inverso al de la pila original.
Es muy importante notar que la variable p se recibe por valor, no se recibe la referencia por lo tanto por más que la utilicemos para recorrer la lista y "la avancemos asignándole su siguiente elemento", cuando este procedimiento finalice, en el programa principal p no habra sufrido ninguna modificación.
Obviamente, más claro hubiera sido utilizar otra variable.
Por último vemos el desarrollo de las operaciones para manejar la pila: poner y sacar.
CalculadoraRPN.pas
1:
2:uses untCalculadoraRPN;
3:
4:// variables del programa principal
5:var
6: exp:string[20]; // string para leer por teclado
7: p:PRPila; // pila de la calculadora
8: v1,v2,v3:real; // valores para apilar
9:begin
10: p:=NIL; // inicializo la pila
11: readln(exp); // el usuario ingresa una expresion
12:
13: // 'FIN' => finaliza el programa
14: while( exp<>'FIN' ) do begin
15:
16: // si el usuario ingreso un valor numerico...
17: if( esOperando(exp) ) then begin
18: val(exp,v1); // lo convierto a real
19: poner(p,v1); // lo apilo
20: end else begin
21: // el usuario ingreso un operador...
22: sacar(p,v1); // tomo un valor de la pila
23: sacar(p,v2); // tomo otro valor de la pila
24:
25: // realizo la operacion exp entre v2 y v1
26: v3:=operar(v2,v1,exp);
27:
28: // apilo el resultado
29: poner(p,v3);
30:
31: // muestro el contenido de la pila
32: mostrarPila(p);
33: end;
34:
35: // el usuario ingresa una expresion
36: readln(exp);
37: end;
38:end
39:
untCalculadoraRPN.pas
1:
2:unit untCalculadoraRPN;
3:
4:interface
5: type
6: // :O)
7: PRPila = ^RPila;
8: RPila = record
9: valor: real;
10: sig: PRPila;
11: end;
12:
13: //
14: // funciones de manejo de pila
15: //
16:
17: // pone un elemento en la pila
18: procedure poner(var p: PRPila; v: real);
19:
20: // retorna true o false si hay elementos para
21: // sacar de la pila. Si hay elementos entonces
22: // el elemento que saca lo almacena en v
23: function sacar(var p: PRPila; var v:real):boolean;
24:
25: //
26: // funciones de manejo de operadores
27: //
28:
29: // retorna false si s es alguno de los siguientes
30: // caracteres: '+', '-', '*', '/'
31: function esOperando(s:string[20]):boolean;
32:
33: // retorna el resultado de la operacion entre
34: // los valores v1 y v2, siendo exp alguno de los
35: // operadores soportados por esta calculadora
36: function operar(v1,v2: real; op: string[20]): real;
37:
38: // muestra el contenido de la pila en orden
39: // inverso
40: procedure mostrarPila(p:PRPila);
41:
42:implementation
43:
44:function esOperando(s:string[20]):boolean;
45:begin
46: esOperando:= (s<>'+')
47: AND (s<>'-')
48: AND (s<>'*')
49: AND (s<>'/');
50:end;
51:
52:function operar(v1,v2: real; op: string[20]): real;
53:begin
54: if( op='+' ) then begin
55: operar:=v1+v2;
56: exit;
57: end;
58: if( op='-' ) then begin
59: operar:=v1-v2;
60: exit;
61: end;
62: if( op='*' ) then begin
63: operar:=v1*v2;
64: exit;
65: end;
66: if( op='/' ) then begin
67: operar:=v1/v2;
68: exit;
69: end;
70:end;
71:
72:procedure poner(var p: PRPila; v: real);
73:var nuevo:PRPila;
74:begin
75: new(nuevo);
76: nuevo^.valor:=v;
77: nuevo^.sig:=p;
78: p:=nuevo;
79:end;
80:
81:function sacar(var p: PRPila; var v:real):boolean;
82:var aux:PRPila;
83:begin
84: if( p=NIL ) then begin
85: sacar:=false;
86: exit;
87: end;
88:
89: v:=p^.valor;
90: aux:=p;
91: p:=p^.sig;
92: dispose(aux);
93: sacar:=true;
94:end;
95:
96:
97:procedure mostrarPila(p:PRPila);
98:var aux,x,nuevo:PRPila;
99:begin
100: aux:=NIL;
101:
102: // recorremos la pila (como lista) utilziando p
103: // NOTEMOS que p se recibe por valor (sin var)
104: // por lo tanto aunque aqui la modifiquemos no
105: // quedara modificada en el programa principal
106: // es decir: en el programa principal la variable
107: // p no quedara en NIL
108: while( p<>NIL ) do begin
109: // por cada nodo de p creo un nuevo nodo
110: // para la pila auxiliar
111: new(nuevo);
112: nuevo^.valor:=p^.valor;
113: nuevo^.sig:=aux;
114: aux:=nuevo;
115:
116: // avanzo p
117: p:=p^.sig;
118: end;
119:
120: // saco nodos de la pila auxiliar, los muestro
121: // y los libero
122: while( aux<>NIL ) do begin
123: writeln(': ',aux^.valor:0:2);
124: x:=aux;
125: aux:=aux^.sig;
126: dispose(x);
127: end;
128:end;
129:
130:end.
131:
Algoritmos y Estructuras de Datos UTN - UBA.
