Написать исполнитель нормальных алгоритмов Маркова для заданного алфавита.
| Ввод | Вывод | Комментарий |
|
abbbcaa aa->a bb->b cc->c |
abca | Пройдено |
|
x *x->xx* *=> ->* |
xx | Пройдено |
|
cbabca ba->ab cb->bc ca->ac |
aabbcc | Пройдено |
Прочитав строку и команды нам нужно разделить каждую команду на три элемента: ключ, значение, boolean-переменная (отвечает на вопрос: «Конечная ли команда?»). Последняя переменная нужна для того чтобы определить производится ли окончание операций после данной команды.
После этого я использовал небольшой аналог рекурсии. Дело в том, что я использовал бесконечный вызов функции до того момента, когда сама функция не передаст циклу команду остановиться.
В самой же функции идет поиск каждой команды в заданной строке, вначале по первому символу, а потом, если символ совпал, проверяется идентична ли найденная часть строки одной из наших команд.
Если никакая команда не нашла соответствие, функция возвращает 0 и программа выходит из цикла.
Если же совпадение было найдено, то мы заменяем найденный в строке ключ на соответствующее ему значение и возвращаем boolean-переменную (опять же соответствующую заданному ключу), таким образом если это конечная операция, то будет произведен выход из функции, иначе — будет произведен повторный вызов функции.
Так же следует учитывать и то что пустой ключ указывает на то что значение должно добавиться к началу строки, учтем это при написании кода.
Опробовать код можно здесь: http://ideone.com/QobpUI
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include <cstdlib> #include <iostream> #include <cstring> #include <vector> using namespace std; string s; string *h, *t; int *b; int n; vector<string> p; int step=0; int op; int f() { for( int i=0 ; i<n ; i++ ) // i -- проход команд (h) if( h[i] == "" ) { s = t[i]+s; return b[i]; } else for( int j=0 ; j<(int)s.length() ; j++ ) // j -- поиск нужной команды в строке (s) if( h[i][0] == s[j] ) { //Проверка слова на идентичность int r=0; for( int k=0 ; k<(int)h[i].length() ; k++ ) { if( h[i][k] == s[j+k] ) { r++; } } if( r == h[i].length() ) { // Замена string s1="", s2=""; for( int i1=0 ; i1<j ; i1++ ) { s1 += s[i1]; } for( int i1 = j + h[i].length() ; i1<s.length() ; i1++ ) { s2 += s[i1]; } s = s1 + t[i] + s2; step++; //if(op)cout << "Step#" << step << ": " << s << endl; return b[i]; } } return 0; } int main() { string sm; //------------------------------------------ cin >> s; while( cin>>sm ) { p.push_back(sm); } //cout << "Показывать пошаговые действия?(1\)\n"; //cin >> op; //op = (op?1:0); // небольшой фильтр n = p.size(); h=new string[n]; t=new string[n]; b=new int[n]; for( int i=0 ; i<n ; i++ ) { int j; for( j=0 ; !(p[i][j]=='=' && p[i][j+1]=='>') && !(p[i][j]=='-' && p[i][j+1]=='>') ; j++ ); t[i]=h[i]=""; for( int k=0 ; k<j ; k++ ) h[i]+=p[i][k]; b[i]=(p[i][j]=='='?0:1); for( int k=j+2 ; k<p[i].size() ; k++ ) t[i]+=p[i][k]; } for( ; f() ; ); cout << s << endl; } |