Решите на c++, если хотите отправить решение то проверьте на примерах на фото

Question

Решите на c++, если хотите отправить решение то проверьте на примерах на фото

Влад Иванов Ученик (64), открыт 4 недели назад

Преобразователь строк – это специальная компьютерная программа. Она полу-
чает на вход строку S и набор правил преобразования строки. Каждое из правил

имеет вид c1c2 → ε, где c1 и c2 – маленькие буквы латинского алфавита. Символом
здесь обозначена пустая строка. При этом каждый символ присутствует не более,
чем в одном правиле.
Преобразователь строк работает по шагам. За один шаг он находит в текущей
строке подстроку, совпадающую с правой частью одного из правил, после чего эта

подстрока удаляется из текущей строки (этот процесс называется применением пра-
вила). Этот процесс продолжается до тех пор, пока существует правило, которое

можно применить. Строка, которая остается к моменту, когда нельзя применить
никакое правило, считается результатом T работы преобразователя строк.
Пусть, например, набор правил таков: abε, cd → ε, а исходная строка S = aabbccdba.
Тогда работа преобразователя будет выглядеть так: aabbccdba → abccdba → ccdba →
cba, и результатом T работы преобразователя будет строка cba.
Ваша задача состоит в том, чтобы написать программу, моделирующую работу
преобразователя строк с заданным набором правил на заданной строке S.
Формат входных данных
Первая строка входного файла содержит целое число n(0 ≤ n ≤ 13) – количество

правил. Далее идут n строк, каждая из которых описывает одно из правил. Га-
рантируется, что каждая из маленьких букв латинского алфавита присутствует не

более, чем в одном правиле. Последняя, (n+2)-ая строка входного файла содержит
исходную строку S. Она не пуста и состоит только из маленьких букв латинского
алфавита. Длина S не превосходит 100000.
Формат выходных данных
В выходной файл выведите строку T — результат работы преобразователя на
строке S.

Answer 1

Лови

 #include  
#include  
#include  
#include  
#include  
#include  
 
int main() { 
    std::ifstream inputFile("INPUT.TXT"); 
    std::ofstream outputFile("OUTPUT.TXT"); 
 
    int n; 
    inputFile >> n; 
 
    std::unordered_map rules; 
    for (int i = 0; i < n; ++i) { 
        std::string rule; 
        inputFile >> rule; 
        rules[rule.substr(0, 2)] = ""; 
    } 
 
    std::string S; 
    inputFile >> S; 
 
    std::stack charStack; 
 
    for (char c : S) { 
        charStack.push(c); 
 
        while (charStack.size() >= 2) { 
            char top1 = charStack.top(); 
            charStack.pop(); 
            char top2 = charStack.top(); 
            charStack.pop(); 
 
            std::string substr = std::string(1, top2) + std::string(1, top1); 
 
            if (rules.find(substr) != rules.end()) { 
                continue; 
            } else { 
                charStack.push(top2); 
                charStack.push(top1); 
                break; 
            } 
        } 
    } 
 
    std::string result; 
    while (!charStack.empty()) { 
        result += charStack.top(); 
        charStack.pop(); 
    } 
 
    std::reverse(result.begin(), result.end()); 
 
    outputFile << result; 
 
    inputFile.close(); 
    outputFile.close(); 
 
    return 0; 
}