|
Programa que traduce de notacion infija a postfija Recuerde que para esta parte del programa se va a suponer que la expresión que digita el usuario no tiene errores, luego se darán consejos para detectarlos. En los ejemplos de la sección anterior se observó que para realizar la traducción de la expresión se necesitan dos pilas de Strings (texto), una para los números y otra para los operadores. JAVA ya posee una clase que maneja pilas, esta clase se llama Stack que se encuentra dentro del paquete java.util, lo primero que tenemos que hacer es llamar a esta librería y hacer nuestra clase Parseador6; el inicio de nuestro programa se debe ver como:
import java.util.*;
public class Parseador{
...
}//fin de Parseador
Para crear una nueva pila se debe definir como un nuevo objeto:
Stack nuevaPila = new Stack();
La clase Stack se maneja con objetos (introduce objetos y saca objetos); para introducir un nuevo objeto dentro de la pila se utiliza la instrucción
nuevaPila.push(Objeto);
Para sacar un objeto de la pila (recuerde que una pila saca el último objeto que se introdujo) utilizamos
nuevaPila.pop();
Para "mirar'' un objeto de la pila sin sacarlo se usa
nuevaPila.peek()
Además se puede preguntar si la pila está vacía con la instrucción
nuevaPila.empty()
que devuelve True si está vacía o False si no lo está. Para empezar con la clase Parseador, definimos la variable global ultimaParseada como sigue:
private String ultimaParseada;
Esta guarda un registro de la última expresión parseada (o traducida) en notación postfija, la expresión se guarda por si alguien quiere evaluar sin tener que dar la expresión en donde se evalúa. El constructor de nuestra clase lo único que hace es poner ultimaParseada en 0.
public Parseador(){
ultimaParseada="0";
}
La función parsear se define de tal forma que recibe un texto con la expresión en notación infija y devuelve otro texto con la expresión en notación postfija. La función lanza una excepción (SintaxException) si encuentra que la expresión está mal digitada.
public String parsear(String expresion) throws SintaxException{
Stack PilaNumeros=new Stack(); //Pila de números
Stack PilaOperadores= new Stack(); //Pila de operadores
String fragmento;
int pos=0, tamano=0;
byte cont=1;
final String funciones[]={"1 2 3 4 5 6 7 8 9 0 ( ) x e + - * / ^ %",
"pi",
"ln(",
"log( abs( sen( sin( cos( tan( sec( csc( cot( sgn(",
"rnd() asen( asin( acos( atan( asec( acsc( acot( senh( sinh( cosh( tanh(
sech( csch( coth( sqrt(",
"round( asenh( acosh( atanh( asech( acsch( acoth("};
final private String parentesis="( ln log abs sen sin cos tan sec csc cot asen asin
acos atan asec acsc acot senh sinh cosh tanh sech csch coth sqrt round";
final private String operadoresBinarios="+ - * / ^ %";
//La expresión sin espacios ni mayúsculas.
String expr=quitaEspacios(expresion.toLowerCase());
La función necesita dos pilas: PilaNumeros y PilaOperadores. La variable fragmento se encargará de guardar el fragmento de texto (String) que se esté utilizando en el momento (ya sea un número, un operador, una función, etc.). La variable pos va a marcar la posición del caracter que se está procesando actualmente en el String. La variable funciones contiene un arreglo de textos (String), en la primera posición tiene todas las expresiones de un caracter que se aceptarán, en la segunda posición están las expresiones de dos caracteres y así hasta llegar a la posición seis. La variable parentesis contiene a todas las expresiones que funcionarán como paréntesis de apertura. En operadoresBinarios se guardan todos los operadores que reciben dos parámetros. Todas estas definiciones se hacen como texto (String) para después poder comparar si la expresión que el usuario digitó concuerda con alguno de ellos. Se define también el String en donde se guarda la expresión sin espacios ni mayúsculas (expr); la función toLowerCase() ya está implementada en JAVA en la clase String mientras que quitaEspacios es una función que se define de la siguiente manera
private String quitaEspacios(String expresion){
String unspacedString = ""; //Variable donde guarda la función
//Le quita los espacios a la expresión que leyó
for(int i = 0; i < expresion.length(); i++){
if(expresion.charAt(i) != ' ')
unspacedString += expresion.charAt(i);
}//for
return unspacedString;
}//quitaEspacios
Esta función va tomando cada uno de los caracteres de la expresión, si el caracter no es un espacio lo agrega al texto sin espacios unspacedString. La excepción que lanza el programa también se define como una clase privada
private class SintaxException extends ArithmeticException{
public SintaxException(){
super("Error de sintaxis en el polinomio");
}
public SintaxException(String e){
super(e);
}
}
Volviendo a la función parsear, lo que seguiría es realizar un ciclo mientras no se acabe la expresión, es decir
try{
while(pos<expr.length()){
Lo que se haría dentro del while es ver si lo que sigue en la expresión es algo válido y tomar decisiones dependiendo si es un número, un operador, un paréntesis o una función. El código:
tamano=0;
cont=1;
while (tamano==0 && cont<=6){
if(pos+cont<=expr.length() &&
funciones[cont-1].indexOf(expr.substring(pos, pos+cont))!=-1){
tamano=cont;
}
cont++;
}
Hace que el contador vaya de 1 a 6 que es la máxima cantidad de caracteres que tiene una función y se inicializa tamano en cero. Luego se pregunta si la posición actual (pos) más el contador (cont) es menor de la longitud del texto y si el fragmento de texto que sigue está en alguna de las funciones, si esto pasa el siguiente texto que se tiene que procesar es de tamaño cont. Ahora se van tomando algunos casos con respecto al tamaño encontrado.
if (tamano==0){
ultimaParseada="0";
throw new SintaxException("Error en la expresión");
Si tamano continúa siendo cero quiere decir que el fragmento de texto que sigue no coincidió con ninguna función ni con algo válido por lo que se lanza una excepción y se pone la última expresión parseada en 0.
}else if(tamano==1){
Pero si el tamaño es uno tenemos varias opciones, la primera es que sea un número
if(isNum(expr.substring(pos,pos+tamano)){
fragmento="";
do{
fragmento=fragmento+expr.charAt(pos);
pos++;
}while(pos<expr.length() && (isNum(expr.substring(pos,pos+tamano)) ||
expr.charAt(pos) == '.' || expr.charAt(pos) == ','));
try{
Double.parseDouble(fragmento);
}catch(NumberFormatException e){
ultimaParseada="0";
throw new SintaxException("Número mal digitado");
}
PilaNumeros.push(new String(fragmento));
pos--;
En la primera línea, para preguntar si el caracter es un número se utiliza la función isNum definida por
private boolean isNum(char s) {
if (s >= '0' && (s <= '9'))
return true;
else
return false;
} //Fin de la funcion isNum
Que devuelve True si el caracter que recibe es un número (está entre 0 y 9) o False si no lo es. Si el caracter actual es un número existe un problema, no se sabe cuántos dígitos tenga este número, por lo que se sacan todos los caracteres que sigan que sean números, puntos o comas. En la variable fragmento se va a guardar el número, por lo que al inicio se debe vaciar (fragmento=" ''). Luego se hace un ciclo mientras no se acabe la expresión y el caracter que sigue sea un número, un punto o una coma: while(pos Luego, la variable fragmento se trata de convertir a double y se mete en la pila de números; si no la puede convertir el programa lanza una excepción en el bloque try-catch. De esta manera se maneja un número cualquiera. Ahora la segunda posibilidad con tamaño uno es que el caracter sea
else if (expr.charAt(pos)=='x' || expr.charAt(pos)=='e'){
PilaNumeros.push(expr.substring(pos,pos+tamano));
Si el caracter que sigue es uno de los operadores +, *, / y % (el menos `-' se maneja igual, pero se recomienda ponerlo en un caso aparte para manejar posteriormente los menos unarios) se deben sacar todos los operadores con prioridad mayor o igual a ellos y meter el operador en la pila
}else if (expr.charAt(pos)=='+' || expr.charAt(pos)=='*' ||
expr.charAt(pos)=='/' || expr.charAt(pos)=='%'){
sacaOperadores(PilaNumeros, PilaOperadores, expr.substring(pos,pos+tamano));
En este caso se declara una función (ya que se utilizará mucho al manejar detalles posteriores) que realice el trabajo de sacar operadores de la pila, esta función se define de la siguiente manera
private void sacaOperadores(Stack PilaNumeros, Stack PilaOperadores, String operador){
final String parentesis="( ln log abs sen sin cos tan sec csc cot sgn asen asin
acos atan asec acsc acot senh sinh cosh tanh sech csch coth sqrt round asenh
asinh acosh atanh asech acsch acoth";
while(!PilaOperadores.empty() &&
parentesis.indexOf((String)PilaOperadores.peek( ))==-1 &&
((String)PilaOperadores.peek()).length()==1 &&
prioridad(((String)PilaOperadores.peek()).charAt(0))>=
prioridad(operador.charAt(0))){
sacaOperador(PilaNumeros, PilaOperadores);
}
PilaOperadores.push(operador);
}
Aquí se vuelve a declarar la variable parentesis para el while. En este while se indica que se deben sacar operadores mientras haya algo en la pila, lo que siga en la pila no sea un paréntesis, sea de un solo caracter y cuya prioridad sea mayor o igual a la prioridad del operador que se está procesando en ese momento; luego se guarda el operador en la pila correspondiente. Observe que el while llama a sacaOperador que es una función definida posteriormente cuyo código es
private void sacaOperador(Stack Numeros, Stack operadores) throws EmptyStackException{
String operador, a, b;
final String operadoresBinarios="+ - * / ^ %";
try{
operador=(String)operadores.pop();
if(operadoresBinarios.indexOf(operador)!=-1){
b=(String)Numeros.pop();
a=(String)Numeros.pop();
Numeros.push(new String(a+" "+b+" "+operador));
}else{
a=(String)Numeros.pop();
Numeros.push(new String(a+" "+operador));
}
}catch(EmptyStackException e){
throw e;
}
}//sacaOperador
Esta función se encarga de sacar dos números de la pila correspondiente, esto si es un operador binario o un número si es unario; luego introduce el nuevo número en notación postfija en la pila. Esta función recibe las dos pilas y no devuelve nada, si se le acaban los elementos a alguna de las pilas se lanza una excepción. Esta es la última función externa que se va a necesitar para traducir la expresión. Con la potencia (^) es más sencillo ya que este operador no saca a nadie, el código quedaría de la siguiente manera.
}else if (expr.charAt(pos)=='^'){
PilaOperadores.push(new String("^"));
En este caso, simplemente se mete el operador a su pila correspondiente. Si el caracter fuera un paréntesis de apertura simplemente se mete en la pila de operadores.
}else if (expr.charAt(pos)=='('){
PilaOperadores.push(new String("("));
Y si el caracter es un paréntesis de cierre se deben sacar operadores hasta encontrar una apertura de paréntesis en la pila.
}else if (expr.charAt(pos)==')'){
while(!PilaOperadores.empty() &&
parentesis.indexOf(((String) PilaOperadores.peek()))==-1){
sacaOperador(PilaNumeros, PilaOperadores);
}
if(!((String)PilaOperadores.peek()).equals("(")){
PilaNumeros.push(new String(((String)PilaNumeros.pop()) + " " +
PilaOperadores.pop()));
}else{
PilaOperadores.pop();
}
}
Si el paréntesis de apertura no era el caracter "('' (es decir, era una función) entonces la concatena al final del texto en la notación postfija, si era un paréntesis simplemente lo desecha (recuerde que en notación postfija no hay paréntesis). Aquí se terminan de procesar todos los elementos posibles de un solo caracter, ahora se pasará al caso de dos o más caracteres
}else if(tamano>=2){
fragmento=expr.substring(pos,pos+tamano);
if(fragmento.equals("pi")){
PilaNumeros.push(fragmento);
}else if(fragmento.equals("rnd()")){
PilaNumeros.push("rnd");
}else{
PilaOperadores.push(fragmento.substring(0,fragmento.length()-1));
}
}
pos+=tamano;
}//Fin del while
En este caso se toma la expresión en fragmento, si fragmento es igual a "pi'', lo metemos en la pila de números; lo mismo hacemos si es rnd(). Cualquier otra posibilidad de tamaño mayor que dos es que sea una función por lo que se mete en la pila de operadores quitándole el paréntesis. Al final se aumenta la posición de acuerdo al tamaño del texto procesado para pasar al siguiente caracter en la expresión. Ya cuando se acabó la expresión se debe procesar todo lo que quedó en las pilas en el proceso final, esto se hace con un while que saque todos los operadores que quedaron
//Procesa al final
while(!PilaOperadores.empty()){
sacaOperador(PilaNumeros, PilaOperadores);
}
}catch(EmptyStackException e){
ultimaParseada="0";
throw new SintaxException("Expresión mal digitada");
}
ultimaParseada=((String)PilaNumeros.pop());
if(!PilaNumeros.empty()){
ultimaParseada="0";
throw new SintaxException("Error en la expresión");
}
return ultimaParseada;
}//Parsear
Si hubo algún error con las pilas en el proceso se lanza una excepción y se pone a ultimaParseada en cero. Al final se devuelve ultimaParseada. Con esto ya acabamos el programa que convierte una expresión matemática del lenguaje natural a la notación postfija.
Cidse - Revista virtual Matemática, Educación e Internet - ITCR
|
expr.length() && (isNum(expr.substring(pos,pos+tamano)) 
expr.charAt(pos) == `.' 
expr.charAt(pos) == `,')){ .
o 
. Estos dos casos se manejan como un número que se mete en la pila.