Решение задачи "Скобочки - 2" с Acmp

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


Напомним, что называется правильной скобочной последовательностью:

пустая строка является правильной скобочной последовательностью;
если строка а — правильная скобочная последовательность, то строки (а), [а] — тоже правильные скобочные последовательности;
если строки а и b — правильные скобочные последовательности, то строка ab — тоже правильная скобочная последовательность.
Задана строка S, состоящая из квадратных и круглых скобок. Разрешается заменять квадратную открывающую скобку ([) на круглую открывающую (() и наоборот, а также квадратную закрывающую скобку (]) на круглую закрывающую ()) и наоборот.

За одно действие разрешается изменить ровно один символ строки. Необходимо за минимальное число действий преобразовать S в правильную скобочную последовательность.

Код

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int k = 0, k1 = 0;
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '(' &&  s[i + 1] == ')'){
            s.erase(i, 2);
            i-=2;
        }
        else if(s[i] == '[' &&  s[i + 1] == ']'){
            s.erase(i, 2);
            i-=2;
        }
        if(i < 0)
            i = -1;
    }
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == ']' || s[i] == ')')
            ++k;
        else
            ++k1;
    }
    if(k != k1){
        cout << -1;
        return 0;
    }
    int c = 0;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '(' &&  s[i + 1] == ']'){
            s.erase(i, 2);
            i-=2;
            c++;
        }
        else if(s[i] == '[' &&  s[i + 1] == ')'){
            s.erase(i, 2);
            i-=2;
            c++;
        }
        else if(s[i] == '(' &&  s[i + 1] == ')'){
            s.erase(i, 2);
            i-=2;
        }
        else if(s[i] == '[' &&  s[i + 1] == ']'){
            s.erase(i, 2);
            i-=2;
        }
        if(i < 0)
            i = -1;
    }
    if(s.size())
        cout << -1;
    else
        cout << c;
    return 0;
}

         

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


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

Комментарии

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