Problem
In C++ bindet RAII eine Ressource an die Lebensdauer eines Objekts: Die Ressource wird automatisch freigegeben, wenn das Objekt den Scope verlässt. Objekte im selben Scope werden in umgekehrter Erzeugungsreihenfolge zerstört.
Verarbeite die Events der Reihe nach:
{: betritt einen neuen inneren Scope.}: verlässt den aktuellen Scope; jede darin angelegte Ressource wird freigegeben, die neueste zuerst.acquire <name>: legt eine Ressource im aktuellen Scope an.
Wenn keine Events mehr kommen, enden die noch offenen Scopes vom innersten bis zum äußersten (einschließlich des äußeren Programm-Scopes) und geben ihre Ressourcen auf dieselbe Weise frei.
Implementiere raii_release_order(events).
Eingabe
events: Die Events. Klammern sind ausgeglichen oder bleiben offen, werden aber nie geschlossen, ohne geöffnet zu sein.
Ausgabe
Gib die Ressourcennamen in der Reihenfolge ihrer Freigabe zurück.
Einschränkungen
0 ≤ Anzahl der Events ≤ 100,000
Namen haben 1 bis 20 Zeichen ohne Leerzeichen
Beispiele
Eingabe:
events = ["acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"]
Erwartete Ausgabe:
expected = ["lock", "file", "log", "db"]Eingabe:
std::vector<std::string> events = {"acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"};
Erwartete Ausgabe:
std::vector<std::string> expected = {"lock", "file", "log", "db"};Eingabe:
string[] events = new string[] {"acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"};
Erwartete Ausgabe:
string[] expected = new string[] {"lock", "file", "log", "db"};Erläuterung
Das Verlassen des inneren Scopes gibt lock und dann file frei (die neueste zuerst). Am Ende gibt der äußere Scope log und dann db frei: ["lock", "file", "log", "db"].
Eingabe:
events = ["{", "acquire a", "{", "acquire b"]
Erwartete Ausgabe:
expected = ["b", "a"]Eingabe:
std::vector<std::string> events = {"{", "acquire a", "{", "acquire b"};
Erwartete Ausgabe:
std::vector<std::string> expected = {"b", "a"};Eingabe:
string[] events = new string[] {"{", "acquire a", "{", "acquire b"};
Erwartete Ausgabe:
string[] expected = new string[] {"b", "a"};Erläuterung
Am Ende sind noch zwei Scopes offen: Der innerste gibt b frei, dann der nächste a: ["b", "a"].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Führe einen Stack von Scopes, die ihre Ressourcen in Reihenfolge speichern.
Hinweis 2
Das Schließen eines Scopes gibt seine Ressourcen von der neuesten zur ältesten frei.
Hinweis 3
Schließe am Ende alle noch offenen Scopes, den innersten zuerst.
Erwartete Komplexität
Zeit O(Anzahl der Events), zusätzlicher Speicher O(Anzahl der Events)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.