Решение задачи Распознавание языка с Acmp

Без пояснения   Просмотров: 240

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

В этой задаче необходимо проверить, принадлежит ли данное слово языку {0n1n2n, n ≥ 1}. В этот язык входят те и только те слова, которые имеют такую структуру: в них нулей столько же, сколько единиц, а единиц - столько же, сколько и двоек. При этом любой ноль находится ближе к началу слова, чем любая единица, а любая единица находится ближе к началу слова, чем любая двойка. Например, слово 001122 принадлежит этому языку, а слово 0000111122220 - не принадлежит.

Код 

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n, pos;
    string s;
    cin >> n;
    bool b = false, b1 = false, b2 = false, d = false;
    for(int i = 0; i < n; ++i){
 
        cin >> s;
        b = false; b1 = false; b2 = false; d = false;
        if(s[0] != '0'){
            cout << "NO";
            d = true;
        }
        else{
            b = true;
            for(int j = 1; j < s.size(); ++j){
                if(s[j] == '0')
                    if(b && (b1 || b2)){
                        cout << "NO";
                        d = true;
                        break;
                    }
                if(s[j] == '1'){
                     if(b2){
                        cout << "NO";
                        d = true;
                        break;
                     }
                     else
                        b1 = true;
                }
                if(s[j] == '2')
                    if(!b1){
                        cout << "NO";
                        d = true;
                        break;
                    }
                    else
                        b2 = true;
            }
            if(!d){
                pos = s.find("1");
            if((s.size() - 1 - pos - 1) == (pos - 1) * 2)
                cout << "YES";
            else
                cout << "NO";
            }
        }
        cout << endl;
    }
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES bminhojkhon03@gmail.com Карта сайта