0

Неправильная скобочная последовательность.

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

1 = {

2 = (

3 = [

4 = }

5 = )

6 = ]

Так он создал скобочную последовательность Braces. Но, к сожалению, эта скобочная последовательность оказалась неправильной. Помогите превратить эту последовательность в правильную, добавив минимально возможное количество скобок. тут принцип основан на контроле верхушки стека, а не на анализе самой последовательности, то есть: для "1243" будет засчитано "{({}[])}", тогда как "{()}[]" будет правильнее Python:

import sys
from collections import deque

stack = deque()
cout = deque()
for a in sys.stdin.readlines():
    a = a.replace('\t', '').replace('\n', '').replace('\r', '').replace(' ', '')
    for i in list(a):
        if stack:
            x, y = 0, 0
            if i == '1': y = 1
            elif i == '2': y = 2
            elif i == '3': y = 3
            elif i == '4': y = 4
            elif i == '5': y = 5
            elif i == '6': y = 6
            if stack[-1] == '1': x = 1
            elif stack[-1] == '2': x = 2
            elif stack[-1] == '3': x = 3
            elif stack[-1] == '4': x = 4
            elif stack[-1] == '5': x = 5
            elif stack[-1] == '6': x = 6
            if x + 3 == y:
                stack.pop()
        stack.append(i)
    for i in stack:
        if i == '1':
            print('{', end='')
            cout.appendleft('4')
        elif i == '2':
            print('(', end='')
            cout.appendleft('5')
        elif i == '3':
            print('[', end='')
            cout.appendleft('6')
        elif i == '4': print('{}', end='')
        elif i == '5': print('()', end='')
        elif i == '6': print('[]', end='')
    for i in cout:
        if i == '4': print('}', end='')
        elif i == '5': print(')', end='')
        elif i == '6': print(']', end='')
    



C++:

#include <iostream>
#include <deque>
using namespace std;



int main() {
    deque <char> stack(0);
    deque <char> print(0);
    string a;
    cin >> a;
    for (char i : a) {
        if (stack.size() > 0) {
            int x = atoi(&stack.back()), y = atoi(&i);
            if (x + 3 == y) {
                stack.pop_front();
            }
        }
        stack.push_back(i);
    }
    for (char i : stack) {
        if (i == '1') { cout << '{'; print.push_front('4'); }
        if (i == '2') { cout << '('; print.push_front('5'); }
        if (i == '3') { cout << '['; print.push_front('6'); }
        if (i == '4') { cout << "{}"; }
        if (i == '5') { cout << "()"; }
        if (i == '6') { cout << "[]"; }
    }
    for (char i : print) {
        if (i == '4') { cout << '}'; }
        if (i == '5') { cout << ')'; }
        if (i == '6') { cout << ']'; }
    }
    return 0;
}

решение неправильное, валится на 4 тестах, сами тесты неизвестны, как улучшить код?ссылка на курс с задачей сама задача находится в модуле 1.2 6-ая задача

5
  • По-моему, я уже болел этим дежа вю... Похоже, предыдущие вопросы на эту тему просто удалены.
    – Harry
    18 сен в 10:40
  • ответа я не получил, а решение все же интересно.. 18 сен в 10:43
  • Но в 1.2.6 нет условия "на контроле верхушки стека, а не на анализе самой последовательности"...
    – Harry
    18 сен в 10:45
  • по видео из курса можно понять, что от нас требуют контроля верхушки стека, да и в комментариях об этом говорят 18 сен в 10:48
  • Да в принципе вроде несложно, но совершенно нет времени... Если до вечера никто не сделает, попробую посмотреть...
    – Harry
    18 сен в 10:51

1 ответ 1

0

Так, выдрал немного времени, вот решение на С++ (писалось на бегу, можно оптимизировать, и даже существенно, я этого не делал, лишь бы заработало...)

#include <string>
#include <iostream>

using namespace std;


int main(int argc, char * argv[])
{
    string r = "123", t = "{([})]", s;
    cin >> s;

    for(int i = 0; i < s.size(); ++i)
    {
        if (r.find(s[i]) != r.npos) continue;
        // Какая ближайшая непарная?
        bool found = false;
        for(int j = i-1; j >= 0; --j)
        {
            if (!isdigit(s[j])) continue;
            if (s[j] == s[i] - 3)
            {
                s[j] = t[s[j]-'0'-1];
                s[i] = t[s[i]-'0'-1];
                found = true;
            }
            break;
        }
        if (!found) s[i] += 10;
    }

    for(int i = s.size()-1; i >= 0; --i)
    {
        if (isdigit(s[i]))
        {
            s += t[s[i]-'0'-1+3];
            s[i] = t[s[i]-'0'-1];
        }
    }

    for(int i = 0; i < s.size(); ++i)
    {
        if (isdigit(s[i])) cout << t[s[i]-'0'-1];
        else if (t.find(s[i]) != t.npos) cout << s[i];
        else
        {
            s[i] -= 10;
            cout << t[s[i]-'0'-4] << t[s[i]-'0'-1];
        }
    }
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.