Práctica #3: Pilas y filas

Descripción

Esta actividad se debe realizar y entregar por equipos.

NOTA: Los archivos necesarios para comenzar esta práctica están disponibles en el repositorio de GitHub del curso.

En el archivo fuente llamado stacks_and_queues.cpp, escribe el código de C++ que resuelva los siguientes dos problemas. Debes utilizar las clases stack y/o queue provistas en la biblioteca estándar de C++.

IMPORTANTE: Antes de la definición de cada función debes incluir un comentario que indique su correspondiente complejidad de tiempo.

1. int postfix_evaluation(const std::string& expr)

   Regresa el resultado de evaluar la expresión posfija contenida en la cadena expr que se recibe como entrada. Lanza la excepción std::invalid_argument si expr contiene una expresión inválida.

   Descripción del algoritmo: Empieza con una pila de enteros vacía. Procesa cada elemento contenido en expr en orden:

   • 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.
   • Lanza una excepción si encuentras un elemento que no sea un número o un operador válido (+, -, * o /).

   Si al final la pila contiene un solo valor, ese es el resultado que debes devolver. De lo contrario lanza una excepción.

   TIP #1: Utiliza la función split definida a continuación para extraer los números y operadores de la cadena input. La función devuelve una fila con las cadenas que corresponden a los elementos individuales de la entrada. Por ejemplo, si la entrada es:

       "1 15 10+2*+"

   el resultado devuelto es una fila con estos elementos:

       {"1", "15", "10", "+", "2", "*", "+"}

   #include <queue>
   #include <regex>
   
   std::queue<std::string> split(const std::string& input)
   {
       std::regex exp(R"((\d+)|(\s)|(.))");
       std::smatch match;
       std::string next_input = input;
       std::queue<std::string> result;
   
       while(regex_search(next_input, match, exp)) {
           if (match[2] == "") {
               result.push(match[0]);
           }
           next_input = match.suffix();
       }
   
       return result;
   }
   

   TIP #2: Para determinar si un char es un dígito decimal puedes usar la función isdigit.

   TIP #3: Para convertir una cadena de caracteres a un entero puedes usar la función stoi.

2. bool balanced_brackets(const std::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 se encuentra 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.

Prueba tu código utilizando las pruebas contenidas en el archivo tests.cpp (contiene 30 aserciones en total).

¿Qué se debe entregar?

Coloca en un comentario en la parte superior del archivo fuente stacks_and_queues.cpp la información personal de los autores (matrícula y nombre), por ejemplo:

/*----------------------------------------------------------
 * Práctica #3: Pilas y filas
 * Solución de problemas que usan estructuras FIFO y LIFO.
 *
 * Fecha: 24-Sep-2021
 * Autores:
 *           A01770771 Sylvie Laufeydottir
 *           A01777771 Loki Laufeyson
 *----------------------------------------------------------*/

Solo es necesario que lo entregue un miembro del equipo.

La fecha límite es el martes 5 de octubre.