問題
C++ では、RAII はリソースをオブジェクトの生存期間に結びつけます。オブジェクトがスコープを抜けると、リソースは自動的に解放されます。同じスコープ内のオブジェクトは、作成順の逆順で破棄されます。
イベントを順に処理してください:
{: 新しい内側のスコープに入る。}: 現在のスコープを抜ける。そこで獲得した各リソースは、最後に獲得したものから順に解放される。acquire <name>: 現在のスコープでリソースを作成する。
イベントが尽きたとき、残っている開いたスコープは、最内側から最外側へ（プログラムの外側のスコープを含む）終了し、それぞれのリソースは同じ方法で解放されます。
raii_release_order(events) を実装してください。
Input
events: イベントです。波括弧は対応しているか、開いたまま終わるだけで、閉じるときは必ず開かれてからです。
Output
リソース名を、解放された順に返してください。
制約
0 ≤ イベントの数 ≤ 100,000
名前は空白を含まない 1〜20 文字
例
例 1
入力：
events = ["acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"]
期待される出力：
expected = ["lock", "file", "log", "db"]入力：
std::vector<std::string> events = {"acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"};
期待される出力：
std::vector<std::string> expected = {"lock", "file", "log", "db"};入力：
string[] events = new string[] {"acquire db", "{", "acquire file", "acquire lock", "}", "acquire log"};
期待される出力：
string[] expected = new string[] {"lock", "file", "log", "db"};解説
内側のスコープを抜けると lock سپس file の順に解放されます（新しいものから）。最後に外側のスコープで log سپس db が解放されます: ["lock", "file", "log", "db"].
例 2
入力：
events = ["{", "acquire a", "{", "acquire b"]
期待される出力：
expected = ["b", "a"]入力：
std::vector<std::string> events = {"{", "acquire a", "{", "acquire b"};
期待される出力：
std::vector<std::string> expected = {"b", "a"};入力：
string[] events = new string[] {"{", "acquire a", "{", "acquire b"};
期待される出力：
string[] expected = new string[] {"b", "a"};解説
終了時点で2つのスコープが開いたままです。最内側では b が解放され、その後に次のスコープで a が解放されます: ["b", "a"].
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
スコープのスタックを持ち、各スコープにリソースを順番に記録します。
ヒント 2
スコープを閉じると、新しいリソースから順に解放されます。
ヒント 3
最後に、開いたままのスコープを内側から順に閉じます。
目安の計算量
時間 O(イベントの数)、追加メモリ O(イベントの数)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。