Crear función en java

Respuesta de
luk_tk
Usuario
Escribir una función en java que me permita indicar si una expresión artimetica esta correctamente parentizada.
La función debe indicar si hay un paréntesis incorrecto, por ejemplo si la expresión a revisar es :
{ ( 3 + 4) } * { 7 + 8) } , la función debe retornar < ) , 13 >, es decir, el paréntesis ) ubicado en la posición 13 ( sin considerar los espacios en blanco) esta incorrecto. Si la expresión esta correcta, la función debe retornar < OK>. Para separar los token de la expresión ( operadores y operandos) de entrada se debe utilizar el tipo de dato StringTokenizer. Además como sugerencia del problema para ordenar los operadores y los operandos se puede usar una pila, así es que como he tratado de hacerlo y como se pidió en el problema.
Ojala puedan ayudarme a solucionar el problema...
Desde ya muchas gracias!
Avatar
Experto
Hola,
si lo que debe hacer el método es únicamente comprobar si una expresión está correctamente parentizada lo que se me ocurre es tratar la expresión como un String y realizar lo siguiente:
Recorrer todos los caracteres del String.
- Cuando se encuentre con un parentesis/llave/corchete "(/{/[" de apertura: meterlo en una pila.
- Cuando se encuentre un elemento de cierre saca el primer elemento de la pila, si son del mismo tipo, entonces es correcto. Si no son del mismo tipo, entonces hay un error. Si al finalizar hay algún elemento en la pila, entonces se produce otro error.
Ejemplo: [(3+2)]*[3+2). Recorro la cadena. El primer elemento es [, lo meto en la pila. El segundo elemento es (, lo mentó en la pila. Me encuentro un ) y lo comparo con lo que hay en la cima de la pila, que es (, como son del mismo tipo, es correcto. Sigo y encuentro ], saco lo que hay en la cima de la pila, es [, como son del mismo tipo, es correcto. Encuentro [, lo meto en la pila, sigo y encuentro ), lo comparo con la cima de la pila y es [, error. Tomo la posición de ) y lo muestro.
Para comprobar si son del mismo tipo, basta con utilizar la codificación ASCII. Si ( está representado por el número decimal POR, ) será el número X+1.
   Si lo que quieres hacer es comprobar y además realizar las operaciones, yo crearía un árbol en el que los hijos son los números y las raíces son los operadores. Luego recorres el árbol realizando las operaciones para que se hagan en el orden correcto.
Espero que te sirva, un saludo.
Usuario
Más o menos como podría ser el código en java, si me puedes guiar un poco por favor, o pseudocodigo en su defecto, por favor
Gracias!
Avatar
Experto
Supongamos que tienes la expresión en un String:
String expresion;
Creamos una pila:
Stack<Character> pila = new Stack<Character>();
Para recorrerla:
int i = 0;
int posicion = 0;
boolean esCorrecto = true;
while((i < expresion.lenght()) && esCorrecto){
   // Leemos caracter a caracter:
   char caracter = expresion.charAt(i);
   // Si es un elemento de apertura, lo metemos en la pila:
   if((Character.valueOf(caracter).compareTo('(') == 0) ||
       (Character.valueOf(caracter).compareTo('[') == 0) ||
       (Character.valueOf(caracter).compareTo('{') == 0)){
                 pila.push(caracter);
   // Si por el contrario es un caracter de cierre:
   }else if((Character.valueOf(caracter).compareTo(')') == 0) ||
       (Character.valueOf(caracter).compareTo(']') == 0) ||
       (Character.valueOf(caracter).compareTo('}') == 0)){
               // 1) Comprobamos que la pila tiene elementos. Si  no tiene: Error:
               if(pila.empty()){
                           esCorrecto = false;
                           posicion = i;
               }else{
                          // 2) hay elementos, saco el ultimo elemento introducido:
                          char ultimo = pila.pop();
                          // 3) Si no se corresponde con el mismo elemento de cierre que de apertura, error:
                         if(Character.valueOf(ultimo).compareTo('(') == 0){
                                      if(Character.valueOf(ultimo).compareTo(caracter + 1) != 0){
                                                    esCorrecto = false;
                                                    posicion = i;
                                      }
                        }else{
                                     // Aquí es +2 porque los caracteres ASCII { y [ tienen dos posiciones más allá sus correspondientes de cierre } y ]
                                     if(Character.valueOf(ultimo).compareTo(caracter + 2) != 0){
                                                   esCorrecto = fale;
                                                    posicion = i;
                                     }
                        }
            }
}// Fin while
// Comprobacion extra: asegurarnos de que no quedan elementos en la pila
// Si la pila no está vacia, error.
if(!pila.empty()){
   esCorrecto = false;
}
Más o menos este es el código, esta un poco improvisado asique corrige los posibles errores de sintaxis.
Espero que te ayude.
Usuario
Entendí bien lo que tratabas de hacer con el código... si y tiene alguno problemas de sitaxis, pero aquí tu trabajas con los caracteres de un string... con el charAt... la única diferencia es que como lo tengo que trabajar yo es con el "Stringtokenizer".. que es otro objeto de la clase String que me permite capturar "tokens" (palabras) de un String... entonces así obtengo las palabras en vez de tar recorriendo carácter por carácter... o sea que ahora tendría que un "(" seria una palabra o tokens por individual... ¿me entiendes?.. así tengo que trabajarlo yo... entonces no se como y cuando ir capturando los tokens e ir recorriendo la expresión!...
Ojala lo puedas analizar y ver como podría quedar de la manera que te digo yo!
Saludos y muchas gracias!
Avatar
Experto
Lo que hace StringTokenizer es dividir un String en substrings a partir de una cadena que tu le pases. Por ejemplo, si tienes esta cadena:
String cadena = "aaa@bbbbb@cccc";
y utilizas StringTokenizer:
StringTokenizer tokens = new StringTokenizer(cadena, "@");
Con esto tienes una "lista" con las subcadenas aaa, bbbbb, cccc, ya que utilizas el delimitador "@". En cuanto a lo que tu tienes que hacer... puedes dividir tu expresión primero utilizando el delimitador "(", o sea, un elemento de apertura. Luego observas cada token recorriendolos, por ejemplo:
String exrpesion;
StringTokenizer tokens = new StringTokenizer(expresion, "(");
// Recorrer los tokens:
while(tokens.hasMoreTokens()){
   // Obtenemos los tokens y los almacenamos en el String subcadena
   String subcadena = tokens.nextToken();
   // Ahora puedes utilizar otro StringTokenizer para los elementos de cierre:
   StringTokenizer tokensCierre = new StringTokenizer(subcadena, ")");
   // ....
}
Así es como se utiliza StringTokenizer. El problema que veo yo aquí es por ejemplo si tienes una expresión como esta: ((a+b))), con dos paréntesis de apertura seguidos. StringTokenizer no cuenta el numero de paréntesis que hay, cuenta el número de tokens que se genera, en este caso tokens.countTokens() = 1, y debería ser 2, ya que tenemos 2 paréntesis de apertura. Si utilizamos la misma técnica para los elementos de cierre, y hacemos un countTokens(), el resultado sigue siendo 1, y debería ser 3, ya que hay 3 paréntesis. Luego si comparamos uno con otro, no aparecería el error de sintaxis.
No sé si me explico.
Usuario
Claro, eso mismo te iba a preguntar, entonces puede ser que haya que comparar el tokens que corresponde al paréntesis de cierre con un string cierre, o sea me explico..
el tokens capturado por ejemplo.. if(tokens.equalsIgonoreCase( ")" )){ esa pregunta comparara si son de cierre, y lo que debería hacer es ir acumulándolo, con una variable int acumulador que incremente cada vez que esa pregunta sea valida, ¿me entiendes?...
La otra pregunta que te quería hacer es, ¿cuándo ocupamos la pila y cuando mientras obtenemos los tokens de la expresión? dentro del while o fuera?
Avatar
Experto
Acabo de revisar la API de Java (te recomiendo que la utilices, es muy útil y puedes consultar todos los métodos que te proporcionan las diferentes clases, los paquetes, las interfaces... etc).
StringTokenizer tiene el siguiente constructor:
String cadena = "aa@bbbb@ccc";
StringTokenizer st = new StringTokenizer(cadena, "@", true);
Añadiendo true, lo que hace es que almacene también como tokens a la cadena delimitadora, en este caso "@", por lo que st.countTokens() = 5. De esta forma, en el ejemplo que te puse, si cadena = "((a+b)))", sí detectaría el error de que hay un elemento de cierre más del que debería haber:
String cadena = "((a+b)))";
StringTokenizer st = new StringTokenizer(expresion, "(", true);
        System.out.println("Tamaño: " + st.countTokens());
        while(st.hasMoreElements()){
            String cadena = st.nextToken();
            System.out.println("->" + cadena);
            if(cadena.compareTo("(") != 0){
                StringTokenizer st2 = new StringTokenizer(cadena, ")", true);
                System.out.println("Tamaño ->: " + st2.countTokens());
                while(st2.hasMoreElements()){
                    String cadena2 = st2.nextToken();
                    System.out.println("->" + cadena2);
                }
            }
        }
Si pruebas este código, comprobarás como los tamaños son diferentes y se detecta el error.
Por otro lado, a la hora de apilar y desapilar (clase Stack de java), sería dentro del bucle, ya que es donde realizas las comprobaciones.
OJO, debes implementar algún método para que cuando detecte un error en alguno de los caracteres de apertura o de cierre, almacene la posición en la que está y muestre la subcadena como te pide el enunciado.
Espero que te sirva, un saludo.
Usuario
Esta muy bueno el código y super claro, pero me salio una duda con constructor que ocupas de StringTokenizer, porque este tiene 3 parámetros y tu me dices que este toma como tokens a los delimitadores, ¿pero si yo tuviera que tomar espacios en blanco también me los tomaría como tokens?.. de que me serviría entonces, ¿o es solo una forma de comprobar el tamaño de cada token?... porque según lo que entendí tu estas tomando como delimitador los paréntesis, por el ejemplo "((a+b)))", y según mi parecer los delimitadores no serian esos sino como tu bien dijiste el "@", una coma, un punto o cualquier otro, pero una paréntesis es un token de la expresión.. ¿entonces cómo debería quedar o debería usar el otro constructor?
Ojala me lo puedas aclarar, desde ya muchas gracias!
Avatar
Experto
Los parámetros que recibe el tecer constructor de StringTokenizer son, la cadena que deseas dividir, una cadena que será el delimitador, y un valor booleano, que si vale true, a parte de contar los diferentes tokens, cuenta también la cadena delimitadora tantas veces como aparezca en la cadena original, y si vale false, no los tiene en cuenta, es decir, seria como utilizar el segundo constructor StringTokenizer(String cadena, String delimitador).
De todas formas, para resolver esta duda, consulta la API de java, esta perfectamente explicado y es fácil de comprender (aunque viene en inglés):
http://download.oracle.com/javase/6/docs/api/
Usuario
Muchas gracias por la ayuda, me respondió bastantes dudas que tenia. Me fue de mucha utilidad. Saludos!