Práctica #5: Algoritmos usando pilas

Descripción

Esta actividad se debe realizar y entregar por equipos.

En un mismo archivo fuente llamado algoritmos_pilas.cpp, escribe el código de C++ que resuelva los siguientes dos problemas. Debes usar la implementación de la clase Stack<T> contenida en el archivo stack.h que se escribió en clase.

1. bool balanced_brackets(const 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.

2. int postfix_evaluation(const 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 runtime_error declarada en el encabezado stdexcept 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.
   • 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.

   Puedes usar la función split definida a continuación para extraer los números y operadores de la cadena expr y colocarlos dentro del vector vec que se pasa por referencia:

   #include <regex>
   #include <vector>
   
   using namespace std;
   
   void split(const string& input, vector<string>& vec)
   {
       regex exp(R"((\d+)|(\s)|(.))");
       smatch match;
       string s = input;
   
       while(regex_search(s, match, exp)) {
           if (match[2] == "") {
               vec.push_back(match[0]);
           }
           s = match.suffix();
       }
   }
   

   Para determinar si un char es un dígito decimal puedes usar la función isdigit declarada en el encabezado cctype.

   Para convertir una cadena de caracteres a un entero puedes usar la función stoi declarada en el encabezado string.

En la función main coloca código que te permita probar las implementaciones de ambas funciones.

No olvides colocar la matrícula y nombre de todos los miembros del equipo en un comentario en la parte superior de tu archivo fuente.

Solo es necesario que lo entregue en miembro del equipo.