Práctica 3: Ejercicios con pilas y filas

Objetivos

Durante esta actividad, los alumnos serán capaces de:

Resolver e implementar diversos problemas de programación en Java utilizando pilas y filas.

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.

Descripción

Esta actividad puede ser elaborada de manera individual o en parejas.

Escribe una clase llamada mx.itesm.cem.pilasfilas.Exercises. 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.

Sugerencias

Cuando requieras una pila LIFO declara la variable correspondiente de tipo java.util.Deque<E> y asígnale una instancia de la clase java.util.LinkedList<E>. Por ejemplo:
```
Deque<String> stack = new LinkedList<>();
```
La variable stack reconoce los métodos push(String), pop(), peek(), size(), isEmpty(), etc.
Cuando requieras una fila FIFO declara la variable correspondiente de tipo java.util.Queue<E> y asígnale una instancia de la clase java.util.LinkedList<E>. Por ejemplo:
```
Queue<String> queue = new LinkedList<>();
```
La variable queue reconoce los métodos add(String), remove(), element(), size(), isEmpty(), etc.
Para obtener el carácter contenido en cierto índice puedes usar el método charAt(int) sobre la cadena (string) en cuestión.
Para determinar si un carácter es un dígito numérico puedes usar el método estático Character.isDigit(char).
Para convertir una cadena que contiene solo dígitos a un número entero puedes utilizar el método estático 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;
}

Métodos a 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:
- Si encuentras un símbolo de apertura ((, [ o {) debes insertarlo en la pila.
- Si encuentras un carácter de cierre (), ] 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. Lanza la excepción IllegalArgumentException si expr contiene una expresión inválida.

Descripción del algoritmo: Empieza con una pila de enteros vacía. Inserta todos los elementos de expr en una fila (usando el método tokenize definido arriba) y procesa dichos elementos en orden FIFO:
- Si encuentras un número, insértalo en la pila.
- Si encuentras un operador ⊗ (donde ⊗ puede ser +, -, * o /), saca del tope de la pila dos números B y A (o lanza 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.
- Si encuentras algo que no sea un número o un operador válido (+, -, * o /), entonces lanza una excepción.
Si al final la pila contiene un solo elemento, ése es el resultado que debes devolver. De lo contrario lanza 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:
- Si encuentras un número, insértalo en la fila resultante.
- Si encuentras un paréntesis izquierdo (, insértalo en la pila.
- Si encuentras un operador ⊗ (donde ⊗ puede ser +, -, * o /), realiza lo siguiente:
  - Mientras que la pila no esté vacía y además el tope de la pila sea diferente al paréntesis izquierdo (, realiza lo siguiente:
    - Si el elemento del tope de la pila tiene mayor precedencia que ⊗, entonces hay que sacar dicho elemento de la pila e insertarlo en la fila resultante. De lo contrario se debe terminar el ciclo «mientras» más anidado.
  - Inserta ⊗ en la pila.
- Si encuentras un paréntesis derecho ), realiza lo siguiente:
  - Mientras que la pila no esté vacía y además el tope de la pila sea diferente al paréntesis izquierdo (, realiza lo siguiente:
    - Saca el elemento del tope de la pila e insértalo en la fila resultante.
  - Si la pila no está vacía, remueve el paréntesis izquierdo ( 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("/")));
}

Pruebas unitarias

Prueba tu código usando la siguiente clase de JUnit:

package mx.itesm.cem.pilasfilas;

import static org.junit.jupiter.api.Assertions.*;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

import org.junit.jupiter.api.Test;

class ExercisesTest {

    @Test
    public void testBalancedBrackets() {
        assertTrue(Exercises.balancedBrackets(""));
        assertTrue(Exercises.balancedBrackets("(7)"));
        assertTrue(
                Exercises.balancedBrackets("[]{}()([]{})"));
        assertTrue(Exercises.balancedBrackets(
                "[({(([[{}][{}][{}]]))})]"));
        assertFalse(Exercises.balancedBrackets("{"));
        assertFalse(Exercises.balancedBrackets("]({})"));
        assertFalse(Exercises.balancedBrackets("(((("));
        assertFalse(Exercises.balancedBrackets("))))"));
        assertFalse(Exercises.balancedBrackets("(]{)[}"));
        assertFalse(Exercises
                .balancedBrackets("[]{}()[]{})([])"));
        assertFalse(Exercises.balancedBrackets(
                "[[({(([[{}][{}][{}]]))})]"));
    }

    @Test
    public void testMerge() {
        Queue<Integer> q1, q2, qResult;

        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
        qResult = new LinkedList<>();
        assertEquals(qResult, Exercises.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, Exercises.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, Exercises.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));
        assertEquals(qResult, Exercises.merge(q1, q2));
    }

    @Test
    public void testPostfixEvaluation() {
        assertEquals(42, Exercises.postfixEvaluation("42"));
        assertEquals(26,
                Exercises.postfixEvaluation("20 6 +"));
        assertEquals(14,
                Exercises.postfixEvaluation("20 6 -"));
        assertEquals(120,
                Exercises.postfixEvaluation("20 6 *"));
        assertEquals(3,
                Exercises.postfixEvaluation("20 6 /"));
        assertEquals(8, Exercises
                .postfixEvaluation("1 5 2 * 20 6 / - +"));
        assertEquals(108, Exercises.postfixEvaluation(
                "4 8 15 16 23 42 + + + + +"));
        assertThrows(IllegalArgumentException.class,
                () -> Exercises
                        .postfixEvaluation("1 2 3 *"));
        assertThrows(IllegalArgumentException.class,
                () -> Exercises
                        .postfixEvaluation("1 2 3 * * *"));
        assertThrows(IllegalArgumentException.class,
                () -> Exercises.postfixEvaluation("+"));
        assertThrows(IllegalArgumentException.class,
                () -> Exercises.postfixEvaluation("-"));
        assertThrows(IllegalArgumentException.class,
                () -> Exercises.postfixEvaluation("/"));
        assertThrows(IllegalArgumentException.class,
                () -> Exercises.postfixEvaluation(""));
        assertThrows(IllegalArgumentException.class,
                () -> Exercises.postfixEvaluation("1 2 @"));
        assertThrows(IllegalArgumentException.class,
                () -> Exercises.postfixEvaluation(
                        "10 11 + 5 % 13 *"));
    }

    @Test
    public void testConvertInfixToPostfix() {
        assertEquals("42",
                Exercises.convertInfixToPostfix("42"));
        assertEquals("1 2 +",
                Exercises.convertInfixToPostfix("1 + 2"));
        assertEquals("1 2 * 3 +", Exercises
                .convertInfixToPostfix("1 * 2 + 3"));
        assertEquals("1 2 + 3 + 4 +", Exercises
                .convertInfixToPostfix("1 + 2 + 3 + 4"));
        assertEquals("1 2 +",
                Exercises.convertInfixToPostfix("(1 + 2)"));
        assertEquals("1 2 3 4 + + +",
                Exercises.convertInfixToPostfix(
                        "(1 + (2 + (3 + 4)))"));
        assertEquals("1 2 3 * +", Exercises
                .convertInfixToPostfix("1 + 2 * 3"));
        assertEquals("1 2 + 3 *", Exercises
                .convertInfixToPostfix("(1 + 2) * 3"));
        assertEquals("1 2 3 * + 4 +", Exercises
                .convertInfixToPostfix("1 + 2 * 3 + 4"));
        assertEquals("1 2 + 3 4 + *",
                Exercises.convertInfixToPostfix(
                        "(1 + 2) * (3 + 4)"));
        assertEquals("1 2 + 3 4 * 5 / -",
                Exercises.convertInfixToPostfix(
                        "1 + 2 - 3 * 4 / 5"));
        assertEquals("1 2 / 3 * 4 - 5 +",
                Exercises.convertInfixToPostfix(
                        "1 / 2 * 3 - 4 + 5"));
        assertEquals("1 2 / 3 4 * - 5 +",
                Exercises.convertInfixToPostfix(
                        "1 / 2 - 3 * 4 + 5"));
        assertEquals("1 2 3 - + 4 5 / *",
                Exercises.convertInfixToPostfix(
                        "(1 + (2 - 3)) * (4 / 5)"));
        assertEquals("1 2 3 - / 4 5 + *",
                Exercises.convertInfixToPostfix(
                        "1 / (2 - 3) * (4 + 5)"));
        assertEquals("1 2 3 - 4 5 + * /",
                Exercises.convertInfixToPostfix(
                        "1 / ((2 - 3) * (4 + 5))"));
        assertEquals("1 2 3 4 * - 5 + /",
                Exercises.convertInfixToPostfix(
                        "1 / (2 - 3 * 4 + 5)"));
        assertEquals("42",
                Exercises.convertInfixToPostfix("(42)"));
        assertEquals("42", Exercises
                .convertInfixToPostfix("(((42)))"));
        assertEquals("1 2 +",
                Exercises.convertInfixToPostfix("(1 + 2)"));
        assertEquals("1 2 *", Exercises
                .convertInfixToPostfix("(((1) * (2)))"));
    }
}

¿Qué se debe entregar?

Tu archivo fuente de Java debe comenzar con un comentario que contenga el título de la práctica, la fecha y los datos personales de los autores (matrícula y nombre). Por ejemplo:

/*----------------------------------------------------------
 * Práctica 3: Ejercicios con pilas y filas
 * Fecha: 26-Feb-2018
 * Autores:
 *           A01166611 Pepper Pots
 *           A01160611 Anthony Stark
 *----------------------------------------------------------*/

Instrucciones para subir archivo

Para entregar el archivo Exercises.java, ingresa los siguientes datos:

Solicitar NIP

Si la práctica fue desarrollada en pareja, basta que solo uno de los miembros la entregue.

La fecha límite es el lunes 26 de febrero.

Evaluación

Esta actividad será evaluada usando los siguientes criterios:

-10	No se incluyó en comentario los datos de los autores.
10-100	Dependiendo del número de métodos correctamente implementados.
10	El programa no compila.
1	El programa es un plagio total o parcial.