正しいブラケット シーケンス (RSP)


通常の括弧シーケンスは 1 つ以上のタイプの開き括弧と閉じ括弧で構成され、各開き括弧には閉じ括弧があり、（複数のタイプの場合）それらのタイプは重複しません。
正しい SP: 
( ( ) ) ( ) ( ) 
{ } [ ( ) ] ( ) 
{ [ ( { } ) ] } 
無効な SP: 
) ) ( ( ) ) (( 
{ [ ( ] ) } 
( ( ] } 
 
一連の括弧が同じタイプであるかどうかを確認するには、バランスを確認するだけです。
つまり、ゼロ (残高) に等しい変数を開始します。次に、文字列を実行します (やり方がわからない場合は、走れ、バカ!)。開始括弧に達するとバランスが増加し、終了括弧に達するとバランスが減少します。いずれかの段階で残高がマイナスになったり、最後に残高がゼロにならなくなったりした場合、順序は間違っています。

Training problem

オメガラムダ計算

複数の種類のブラケットが存在する場合、すべてが少し複雑になります。そのバランス変数として機能するスタックを作成します。括弧は重複できないため、これが必要です。行を歩いていて開き括弧に遭遇すると、それをスタックにプッシュします。右中括弧に遭遇すると、そのタイプの左中括弧をスタックからポップしようとします。異なるタイプの中括弧がスタック上にある場合、シーケンスは無効になります。スタックが最後に空でない場合、シーケンスも無効になります。

Training problem

ティルダオメガラムダ計算

正しいブラケット シーケンスの生成は、チェックが行われた方法から直接行われます。正確性に違反することなく、新しいブラケットを追加するだけで済みます。これは、再帰的反復によって行われます。もしあなたが彼を知らないなら - BE... ああ、いや、もっと読むことで理解しようとすることができます.ブラケットの 1 つのタイプのコード サンプルを次に示します。
  
#include <vector>
#include <iostream>

使用 名前空間 std;
int n; // 半分の長さ 
ベクトル<文字>答え; // 私たちの答え 

void rec(int balance) {
if (ans.size() == 2 * n) { // もしそうなら、完了 < /span>
for (int i = 0; i < 2 * n; i++)
cout << ans[i] <<< " ";
cout << "\n";
}
if (ans.size() + バランス + 2 <= n * 2) { // チェック、私たち新しい左中かっこを閉じます
// ここで注意してください: シーケンスごとに個別のベクトルを作成する必要はありません 
ans.push_back('(');
rec(残高 + 1);
ans.pop_back(); // これを理解するには、再帰を意識する必要があります。まず、ベクトルに括弧を追加してから、このすべてのコードを再度実行します。 
// つまり、可能であればもう一度括弧を追加します。 
// これは、再帰を終了し始めるまで、つまり、目的の長さに達するまで発生します。 
// ブラケットの削除が開始されます。あなたがこれを理解するなら - おめでとうございます、あなたは素晴らしいです。 
}
if (balance > 0) { // ブラケットを閉じることができる場合は、それを閉じます。 
ans.push_back(')');
rec(バランス - 1);
ans.pop_back();
}
}

 int main()
{
シン>> n;
録音 (0);

    リターン 0;
}
そして今、困難な時期です - あなた自身でいくつかのタイプの括弧のアルゴリズムを書かなければなりません!ムアハハハハハハハハ！

Training problem

PSP世代