Неправильная скобочная последовательность.
Васе подарили строку, состоящую только из цифр от 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-ая задача