C言語の確定スタック・オートマトン（DAS）をシミュレートする

Question

決定性のあるスタック・オートマトンをシミュレートするために必要なUVAの演習を読んでいたところ、次の項目の特定の文字列がDSAによって受け入れられるかどうかは 形式：

入力の最初の行は、テストケースの数を示す整数Cになります。各テストケースの最初の行にはE、T、F、S、Cの5つの整数があり、Eはオートマトンの状態数、Tは遷移数、Fは最終状態の数、Sは初期状態、 Cはそれぞれテスト文字列の数です。次の行にはオートマトンの最終状態を表すFの整数が入ります。次に、それぞれ2つの整数IおよびJと3つのストリングL、TおよびA（ここで、IおよびJ（0≦I、J <E））は遷移状態の起点および終点の状態をそれぞれ表すT線となる。 Lはテープから遷移に読み込まれた文字を表し、Tはスタックの先頭にある記号を表し、Aはこの遷移の最後にスタックの先頭で実行するアクションです。パイルは常にZです。文字列の終わりを表す、またはトランジション文字のスタックの最上部を考慮しないアクションをアンスタックします）。スタックのアルファベットは大文字になります。チェーンAの場合、シンボルは右から左に積み重ねられます（プログラムJFlapと同じように、つまりスタックの新しい上が左の文字になります）。次に、C行にそれぞれ入力文字列を入力します。入力文字列には、小文字と数字が含まれている可能性があります（必ずしも遷移に存在するとは限りません）。

各テストケースの1行目の出力は、次の文字列「ケースG：」を表示する必要があります。ここで、Gはテストケースの数（1から開始）です。オートマトンが文字列を受け入れる場合は "OK"、そうでない場合は "Reject"を出力するC行。例えば

：

Input: 
2 
3 5 1 0 5 
2 
0 0 1 Z XZ 
0 0 1 X XX 
0 1 0 X X 
1 1 1 X £ 
1 2 £ Z Z 
111101111 
110111 
011111 
1010101 
11011 
4 6 1 0 5 
3 
1 2 b A £ 
0 0 a Z AZ 
0 1 a A AAA 
1 0 a A AA 
2 3 £ Z Z 
2 2 b A £ 
aabbb 
aaaabbbbbb 
c1bbb 
abbb 
aaaaaabbbbbbbbb 

これが出力されます：

Output: 
Case 1: 
Accepted 
Rejected 
Rejected 
Rejected 
Accepted 

Case 2: 
Accepted 
Accepted 
Rejected 
Rejected 
Accepted 

私はいくつかの助け、または私はこのDSAをシミュレートすることができますどのように任意のアイデアを必要とする、私は私に解決したコードを求めていないのです私は自分のコードを作成したいのでアイデアは正しいですか？

Answer 1

遷移を維持するには、まずデータ構造が必要です。トランジション構造体にトランジション・クインプループを含むベクトルを使用できます。しかし、あなたは状態が整数であり、インデックス0で状態0から遷移するベクトルを作成するという事実を使うことができます。そのような状態1からインデックス1へ遷移する。これにより、正確な遷移を見つけるための検索時間を短縮できます。

スタック用のstlライブラリでスタックを簡単に使用できます。

int findIndex(vector<quintuple> v)//which finds the index of correct transition otherwise returns -1 

その後、NewStateにしてnewstackシンボルを取得するために、戻り値を使用します。また、あなたはあなたのような関数を使用することができます最初の方法を使用している場合、それはあなたの実装に依存しchnage可能性の機能を検索する必要があります。

または、遷移を示すベクトルとboolフラグの上にforループを使用できます。

2番目の方法では、新しい状態と新しいスタック記号を参照し、適切な遷移が見つかった場合にそれらを設定する関数を使用できます。

入力の場合は、ベクトルやベクトルのようなものを個人的な好みに応じて使用できます。forループを使用してmainメソッドを実装できますが、余分な問題がある場合は、再帰関数を実装できます。それは簡単かもしれません。