Durante esta actividad, los alumnos serán capaces de:
Esta actividad promueve las siguientes habilidades, valores y actitudes: análisis y síntesis, capacidad para resolver problemas, creatividad, y uso eficiente de la informática y las telecomunicaciones.
Esta actividad puede ser elaborada de manera individual o en parejas.
Escribe una clase llamada edd.util.StacksAndQueues. En esta clase deberás colocar únicamente operaciones de utilería (métodos estáticos) para resolver los problemas que se describen a continuación.
En la parte superior del archivo StacksAndQueues.java coloca en comentarios los datos personales de los autores de la tarea. Por ejemplo:
/*-------------------------------------------------------------------- * Práctica 4: Ejercicios con pilas y filas * Fecha: 17-Feb-2014 * Autores: * 1166611 Pepper Pots * 1160611 Anthony Stark *--------------------------------------------------------------------*/
Algunos consejos:
charAt(int) sobre la cadena en cuestión.
Character.isDigit(char).
Integer.parseInt(String).
Para los problemas 3 y 4, puedes auxiliarte del siguiente método estático tokenize que recibe una cadena y la separa en sus elementos básicos, colocándolos en una fila de cadenas. Por ejemplo, si la entrada es la cadena "123 34 7+*-", entonces devuelve una fila con los siguientes elementos: "123", "34", "7", "+", "*" y "-".
public static java.util.Queue<String> tokenize(String in) { java.util.regex.Pattern p = java.util.regex.Pattern .compile("(\\s)|(\\d+)|(.)"); java.util.regex.Matcher m = p.matcher(in); java.util.Queue<String> result = new java.util.LinkedList<String>(); while (m.find()) { if (m.group(1) == null) { result.add(m.group()); } } return result; }
Estos son los métodos que debes implementar:
public static boolean balancedBrackets(String expr)
Devuelve true si la cadena expr que recibe como parámetro contiene una expresión en donde todos sus símbolos de agrupación (paréntesis (), corchetes [] y llaves {}) están correctamente anidados y balanceados. Devuelve false en caso contrario. Se debe ignorar cualquier carácter de expr que no sea paréntesis, corchetes o llaves.
Descripción del algoritmo: Empieza con una pila vacía. Recorre cada uno de los caracteres de expr de izquierda a derecha:
(, [ o {) debes insertarlo en la pila.
), ] o }) debes remover el carácter del tope de la pila y verificar que ambos caracteres hagan pareja. Debes terminar el algoritmo con false si los respectivos caracteres no hacen pareja, o si la pila estaba vacía antes de intentar remover el elemento del tope.
Si al final la pila está vacía debes devolver true, de otra forma debes devolver false.
public static Queue<Integer> merge(Queue<Integer> q1, Queue<Integer> q2)
Devuelve una nueva fila con el resultado de efectuar el algoritmo de mezcla a partir del contenido de las filas q1 y q2. Las filas q1 y q2 deben llegar ya ordenadas de forma ascendente.
Descripción del algoritmo: Empieza con una fila resultante vacía. En cada iteración determina quien tiene al inicio el elemento x más pequeño de entre q1 y q2 (recuerda que tanto q1 y q2 están ordenadas de forma ascendente, por lo que los elementos más pequeños siempre estarán justo al inicio de cada una de estas filas). Remueve a x de la fila que lo contiene y añádelo al final de la fila resultante. Las iteraciones terminan cuando alguna de q1 o q2 queda vacía. Posteriormente hay que copiar a la fila resultante todos los elementos que quedaron en la fila q1 o q2 que aún no está vacía. Finalmente debes regresar la fila resultante.
public static int postfixEvaluation(String expr)
Regresa el resultado de evaluar la expresión posfija contenida en la cadena expr que se recibe como parámetro. Arroja la excepción IllegalArgumentException si expr contiene una expresión inválida.
Descripción del algoritmo: Empieza con una pila vacía. Inserta todos los elementos de expr en una fila (usando el método tokenize) y procesa dichos elementos en orden FIFO:
+, -, * o /), saca del tope de la pila dos números B y A (o arroja una excepción si el tamaño de la pila es menor a dos), e inserta en la pila el resultado de realizar la operación: A ⊗ B.
+, -, * o /), entonces arroja una excepción.
Si al final la pila contiene un solo elemento, ése es el resultado que debes devolver. De lo contrario arroja una excepción.
public static String convertInfixToPostfix(String expr)
Recibe como parámetro la cadena expr que contiene una expresión aritmética en notación infija. Devuelve una cadena con la expresión equivalente en notación posfija. No realiza ningún tipo de validación respecto a la expresión de entrada.
Descripción del algoritmo: Empieza con una pila vacía y una fila resultante vacía. Inserta todos los elementos de expr en otra fila (usando el método tokenize) y procesa dichos elementos en orden FIFO:
(, insértalo en la pila.
+, -, * o /), realiza lo siguiente:
(, realiza lo siguiente:
), realiza lo siguiente:
(, realiza lo siguiente:
( del tope de la pila.
Si al llegar a este punto la pila no está vacía, remueve uno por uno todos elementos de la pila e insértalos en la fila resultante.
Finalmente, devuelve una cadena conformada por la concatenación de todos los elementos de la fila resultante, usando un espacio en blanco como separador entre elementos.
Consejo: Para el algoritmo anterior, puedes usar el siguiente método para determinar si el elemento del tope de la pila tiene mayor precedencia que el operador ⊗:
public static boolean hasHigherPrecedence(String stackTop, String operator) {
return !((stackTop.equals("+") || stackTop.equals("-"))
&& (operator.equals("*") || operator.equals("/")));
}
Prueba tu código usando la siguiente clase de JUnit:
package edd.util; import static org.junit.Assert.*; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import org.junit.Test; public class StacksAndQueuesTest { @Test public void testbalancedBrackets() { assertTrue(StacksAndQueues.balancedBrackets("")); assertTrue(StacksAndQueues.balancedBrackets("(7)")); assertTrue(StacksAndQueues.balancedBrackets("[]{}()([]{})")); assertTrue(StacksAndQueues.balancedBrackets("[({(([[{}][{}][{}]]))})]")); assertFalse(StacksAndQueues.balancedBrackets("{")); assertFalse(StacksAndQueues.balancedBrackets("]({})")); assertFalse(StacksAndQueues.balancedBrackets("((((")); assertFalse(StacksAndQueues.balancedBrackets("))))")); assertFalse(StacksAndQueues.balancedBrackets("(]{)[}")); assertFalse(StacksAndQueues.balancedBrackets("[]{}()[]{})([])")); assertFalse(StacksAndQueues .balancedBrackets("[[({(([[{}][{}][{}]]))})]")); } @Test public void testMerge() { Queue<Integer> q1, q2, qResult; q1 = new LinkedList<>(); q2 = new LinkedList<>(); qResult = new LinkedList<>(); assertEquals(qResult, StacksAndQueues.merge(q1, q2)); q1 = new LinkedList<>(Arrays.asList(3, 4, 6, 6, 7, 8, 10)); q2 = new LinkedList<>(); qResult = new LinkedList<>(Arrays.asList(3, 4, 6, 6, 7, 8, 10)); assertEquals(qResult, StacksAndQueues.merge(q1, q2)); q1 = new LinkedList<>(); q2 = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 6, 10, 15)); qResult = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 6, 10, 15)); assertEquals(qResult, StacksAndQueues.merge(q1, q2)); q1 = new LinkedList<>(Arrays.asList(3, 4, 6, 6, 7, 8, 10)); q2 = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 6, 10, 15)); qResult = new LinkedList<>(Arrays.asList(1, 2, 3, 3, 4, 4, 5, 6, 6, 6, 6, 7, 8, 10, 10, 15)); } @Test public void testPostfixEvaluation() { assertEquals(42, StacksAndQueues.postfixEvaluation("42")); assertEquals(26, StacksAndQueues.postfixEvaluation("20 6 +")); assertEquals(14, StacksAndQueues.postfixEvaluation("20 6 -")); assertEquals(120, StacksAndQueues.postfixEvaluation("20 6 *")); assertEquals(3, StacksAndQueues.postfixEvaluation("20 6 /")); assertEquals(8, StacksAndQueues.postfixEvaluation("1 5 2 * 20 6 / - +")); assertEquals(108, StacksAndQueues.postfixEvaluation("4 8 15 16 23 42 + + + + +")); try { StacksAndQueues.postfixEvaluation("1 2 3 *"); fail(); } catch (IllegalArgumentException e) { } try { StacksAndQueues.postfixEvaluation("1 2 3 * * *"); fail(); } catch (IllegalArgumentException e) { } try { StacksAndQueues.postfixEvaluation("+"); fail(); } catch (IllegalArgumentException e) { } try { StacksAndQueues.postfixEvaluation("-"); fail(); } catch (IllegalArgumentException e) { } try { StacksAndQueues.postfixEvaluation("/"); fail(); } catch (IllegalArgumentException e) { } try { StacksAndQueues.postfixEvaluation(""); fail(); } catch (IllegalArgumentException e) { } try { StacksAndQueues.postfixEvaluation("1 2 @"); fail(); } catch (IllegalArgumentException e) { } try { StacksAndQueues.postfixEvaluation("10 11 + 5 % 13 *"); fail(); } catch (IllegalArgumentException e) { } } @Test public void testConvertInfixToPostfix() { assertEquals("42", StacksAndQueues.convertInfixToPostfix("42")); assertEquals("1 2 +", StacksAndQueues.convertInfixToPostfix("1 + 2")); assertEquals("1 2 * 3 +", StacksAndQueues.convertInfixToPostfix("1 * 2 + 3")); assertEquals("1 2 + 3 + 4 +", StacksAndQueues.convertInfixToPostfix("1 + 2 + 3 + 4")); assertEquals("1 2 +", StacksAndQueues.convertInfixToPostfix("(1 + 2)")); assertEquals("1 2 3 4 + + +", StacksAndQueues.convertInfixToPostfix("(1 + (2 + (3 + 4)))")); assertEquals("1 2 3 * +", StacksAndQueues.convertInfixToPostfix("1 + 2 * 3")); assertEquals("1 2 + 3 *", StacksAndQueues.convertInfixToPostfix("(1 + 2) * 3")); assertEquals("1 2 3 * + 4 +", StacksAndQueues.convertInfixToPostfix("1 + 2 * 3 + 4")); assertEquals("1 2 + 3 4 + *", StacksAndQueues.convertInfixToPostfix("(1 + 2) * (3 + 4)")); assertEquals("1 2 + 3 4 * 5 / -", StacksAndQueues.convertInfixToPostfix("1 + 2 - 3 * 4 / 5")); assertEquals("1 2 / 3 * 4 - 5 +", StacksAndQueues.convertInfixToPostfix("1 / 2 * 3 - 4 + 5")); assertEquals("1 2 / 3 4 * - 5 +", StacksAndQueues.convertInfixToPostfix("1 / 2 - 3 * 4 + 5")); assertEquals("1 2 3 - + 4 5 / *", StacksAndQueues .convertInfixToPostfix("(1 + (2 - 3)) * (4 / 5)")); assertEquals("1 2 3 - / 4 5 + *", StacksAndQueues.convertInfixToPostfix("1 / (2 - 3) * (4 + 5)")); assertEquals("1 2 3 - 4 5 + * /", StacksAndQueues .convertInfixToPostfix("1 / ((2 - 3) * (4 + 5))")); assertEquals("1 2 3 4 * - 5 + /", StacksAndQueues.convertInfixToPostfix("1 / (2 - 3 * 4 + 5)")); assertEquals("42", StacksAndQueues.convertInfixToPostfix("(42)")); assertEquals("42", StacksAndQueues.convertInfixToPostfix("(((42)))")); assertEquals("1 2 +", StacksAndQueues.convertInfixToPostfix("(1 + 2)")); assertEquals("1 2 *", StacksAndQueues.convertInfixToPostfix("(((1) * (2)))")); } }
Sube el archivo StacksAndQueues.java usando el Sistema de Entrega de Tareas Automatizado. Si la práctica fue desarrollada en equipo, basta que solo uno de los miembros la entregue. No se aceptan tareas por ningún otro medio.
Fecha límite: Martes, 18 de febrero.
Esta actividad será evaluada usando los siguientes criterios:
| 100 | La actividad cumple con todos los requerimientos. |
|---|---|
| -10 | No se incluyó en comentario los datos de los autores. |
| 10 | El programa fuente contiene errores sintácticos. |
| 50-90 | El programa produce algunos errores al momento de correrlo. |
| DA | La solución es un plagio. |