模擬C++中的確定性堆棧自動機（DAS）

Question

我讀UVA，我需要模擬一個確定性的堆棧自動機的運動，看 如果某些字符串在下面給定的條目接受或不DSA格式：

第一行輸入將是一個整數C，它表示測試用例的數量。每個測試用例的第一行包含五個整數E，T，F，S和C，其中E表示自動機中狀態的數量，T表示轉換次數，F表示最終狀態的數量，S表示初始狀態， C分別是測試字符串的數量。下一行將包含F個整數，它們表示自動機的最終狀態。然後出現T行，每行有2個整數I和J以及3個字符串L，T和A，其中I和J分別表示過渡狀態的原點和目的地的狀態（0≤I，J <E）。 L代表從磁帶讀入到轉換中的字符，T代表堆棧頂部找到的符號，以及A在該轉換結束時用堆棧頂部執行的動作（用於表示底部的字符堆總是用Z來表示字符串的末尾，或者是不考慮堆棧頂部的動作，以便使用過渡字符£）。堆棧的字母將是大寫字母。對於鏈A，符號從右到左堆疊（與程序JFlap相同，即堆棧的新頂端將是左側的字符）。然後出現C行，每行都有一個輸入字符串。輸入字符串可能包含小寫字母和數字（不一定出現在任何轉換中）。

每個測試用例的第一行中的輸出必須顯示以下字符串「Case G：」，其中G代表測試用例的編號（從1開始）。然後在C行上打印單詞「OK」，如果自動機接受字符串或「拒絕」，否則。

例如：

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庫中使用堆棧中的堆棧。您還需要搜索功能，它可以根據您的實現，如果您使用第一種方法，你可以使用的函數，而像chnage：

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

然後使用返回值來獲得newstate和newstack符號。

或者你可以使用for循環遍歷vector和bool標誌來表示轉換是否被找到。

第二種方法，你可以使用一個函數，它引用新的狀態和新的堆棧符號，如果你找到了適當的轉換就設置它們。

對於輸入你可以使用類似於矢量或矢量的東西取決於個人的品味。你可以用for循環實現你的main方法，但是如果你想要額外的困難，你可以實現一個遞歸函數。可能很簡單。