Problema
En C++, RAII vincula un recurso a la vida de un objeto: el recurso se libera automáticamente cuando el objeto sale de su ámbito. Los objetos en el mismo ámbito se destruyen en orden inverso al de creación.
Procesa los eventos en orden:
{: entra en un nuevo ámbito interno.}: sale del ámbito actual; todo recurso adquirido en él se libera, primero el más nuevo.acquire <name>: crea un recurso en el ámbito actual.
Cuando se agotan los eventos, los ámbitos abiertos restantes terminan desde el más interno hasta el más externo (incluido el ámbito externo del programa), liberando sus recursos de la misma manera.
Implementa raii_release_order(events).
Input
events: Los eventos. Las llaves están balanceadas o quedan abiertas, y nunca se cierran sin haberse abierto.
Output
Devuelve los nombres de los recursos en el orden en que se liberan.
Restricciones
0 ≤ número de eventos ≤ 100,000
Los nombres tienen de 1 a 20 caracteres sin espacios
Ejemplos
Entrada:
events = ["acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"]
Salida esperada:
expected = ["lock", "file", "log", "db"]Entrada:
std::vector<std::string> events = {"acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"};
Salida esperada:
std::vector<std::string> expected = {"lock", "file", "log", "db"};Entrada:
string[] events = new string[] {"acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"};
Salida esperada:
string[] expected = new string[] {"lock", "file", "log", "db"};Explicación
Salir del ámbito interno libera lock y luego file (primero el más reciente). Al final el ámbito externo libera log y luego db: ["lock", "file", "log", "db"].
Entrada:
events = ["{", "acquire a", "{", "acquire b"]
Salida esperada:
expected = ["b", "a"]Entrada:
std::vector<std::string> events = {"{", "acquire a", "{", "acquire b"};
Salida esperada:
std::vector<std::string> expected = {"b", "a"};Entrada:
string[] events = new string[] {"{", "acquire a", "{", "acquire b"};
Salida esperada:
string[] expected = new string[] {"b", "a"};Explicación
Al final quedan dos ámbitos abiertos: el más interno libera b y luego el siguiente libera a: ["b", "a"].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Mantén una pila de ámbitos, cada uno con sus recursos en orden.
Pista 2
Cerrar un ámbito libera sus recursos del más nuevo al más antiguo.
Pista 3
Al final, cierra todos los ámbitos aún abiertos, empezando por el más interno.
Complejidad esperada
tiempo O(número de eventos), espacio extra O(número de eventos)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.