моделировать детерминированный стек стека (DAS) в C ++ - PullRequest
Новая
       16

моделировать детерминированный стек стека (DAS) в C ++

2 голосов
/ 13 июля 2011

Я читал упражнение 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

Выходные данные в первой строке каждого контрольного примера должны отображать следующую строку «Случай G:», где G представляет номер контрольного примера (начиная с 1). Затем 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, я не спрашиваю у меня код, который решает проблему, потому что я хочу создать свой собственный код (идея состоит в том, чтобы учиться правильно ??), но я нужна помощь (идея или псевдокод), чтобы начать реализацию.

1 Ответ

2 голосов
/ 13 июля 2011

Сначала вам нужна структура данных для сохранения переходов. Вы можете использовать вектор со структурой переходов, которая содержит пятерки переходов. Но вы можете использовать тот факт, что состояния являются целочисленными, и создать вектор с индексом 0, переходом из состояния 0; в индексе 1 переходы из состояния 1, как это. Таким образом, вы можете сократить время поиска для поиска правильного перехода.

Вы можете легко использовать стек в библиотеке stl для стека. Вам также нужна функция поиска, которая может изменяться в зависимости от вашей реализации, если вы используете первый метод, вы можете использовать функцию, которая выглядит следующим образом: 

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

затем используйте возвращаемое значение для получения символа newstate и newstack.

Или вы можете использовать цикл for для вектора и флаг bool, который представляет переход найден или нет.

Во втором методе вы можете использовать функцию, которая берет ссылки на новое состояние и новый символ стека и устанавливает их, если вы найдете соответствующий переход.

Для входных данных вы можете использовать что-то вроде вектора или вектора, в зависимости от личного вкуса. Вы можете реализовать свой основной метод с помощью цикла for, но если вам нужны дополнительные трудности, вы можете реализовать рекурсивную функцию. Пусть это будет легко.

...