Скобочные последовательности

@RetykFlash · Регистрация: 22.11.2023

Студворк — интернет-сервис помощи студентам

Дана скобочная последовательность, заданная символами «[», «]», «{», «}», «(», «)». Выведите самую длинную её подстроку, являющуюся правильной скобочной последовательностью.
Внимание. Решение должно работать за O(n).

Формат ввода
Входные данные содержат скобочную последовательность длины от 1 до 100000.

Формат вывода
Выведите требуемую подстроку, возможно пустую. Если максимальных по длине правильных подстрок несколько, то выведите любую.

Ниже предоставлен код моего решения. Неправильный вывод при вводе "[ ] [ [ ]".

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
string f(string input)
{
    string answer;
 
    stack <char> s;
 
    for (char ch : input) {
        switch (ch)
        {
            case '(': s.push(')'); answer += ch; break;
            case '{': s.push('}'); answer += ch; break;
            case '[': s.push(']'); answer += ch; break;
        
            case ')': case '}': case ']':
                if (!s.empty() && s.top() == ch) {
                    s.pop();
                    answer += ch;
                }
                break;
        
            default:
                break;
        }
    }
    
    int i = answer.size() - 1;
    while (!s.empty()) {
        answer[i] -= char(s.top());
        s.pop();
        --i;
    }
    
    return answer;
}
 
int main()
{
    string input;
    cin >> input;
    
    cout << f(input);
 
    return 0;
}

Добавлено через 20 минут
Думал, что задача решается методом поиска палиндромов, поэтому полез в интернет за ним. Нашёл данную статью: https://habr.com/ru/articles/653617/, переделал код под синтаксис плюсов, вставил в свою программу и... она не работает. Я не знаю, как сделать такой алгоритм, который смог бы, приняв строку, вывести правильную последовательность. Что я делаю не так?

@systy257 · 27.11.2023, 13:35

Поиск самого длинного палиндрома к задаче не относится, по моему. Во-первых, () - не палниндром

. Даже если адаптировать задачу так, чтобы () палиндромом считать, все равно (())() не является палиндромом. Решение за O(n) я, кажется, знаю, но не уверен, хотите вы решить сами или нет.

@RetykFlash · 29.11.2023, 21:11 **[ТС]**

Огромное спасибо за ответ! Я уже решил проблему, но всё равно огромное вам спасибо! Для тех, кто, как я, столкнулся с подобной проблемой - ниже предоставлен код решения:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <vector>
#include <map>
 
using namespace std;
 
template <typename T>
void print(T arg)
{
cout << arg << endl;
}
 
template <typename T, typename... Args>
void print(T arg, Args... args)
{
cout << arg << " ";
print(args...);
}
 
class sc_c
{
public:
size_t index;
char value;
sc_c(size_t index, char value)
{
  this->index = index;
  this->value = value;
};
};
 
int main()
{
ios_base::sync_with_stdio(false);
 
string scs;
cin >> scs;
 
vector<bool> complete;
vector<sc_c> sc_stack;
 
map<char, char> sc2sc{
  {']', '['}, {'}', '{'}, {')', '('}};
 
for (size_t i = 0; i < scs.size(); i++)
{
  complete.push_back(false);
  char sc = scs[i];
  switch (sc)
  {
  case '[':
  case '{':
  case '(':
   sc_stack.push_back(sc_c(i, sc));
   break;
 
  case ']':
  case '}':
  case ')':
   if (sc_stack.size() > 0 and sc_stack.back().value == sc2sc[sc])
   {
    complete[i] = true;
    complete[sc_stack.back().index] = true;
    sc_stack.pop_back();
   }
   else
   {
    sc_stack.clear();
   }
 
   break;
  }
}
 
size_t m_size = 0, c_size = 0, m_index = 0;
 
for (size_t i = 0; i < complete.size(); i++)
{
  if (complete[i])
  {
   c_size += 1;
  }
  else
  {
   c_size = 0;
  }
 
  if (c_size > m_size)
  {
  m_size = c_size;
  m_index = i + 1 - m_size;
  }
}
 
print(scs.substr(m_index, m_size));
 
return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@systy257 20 / 12 / 8 Регистрация: 30.10.2023 Сообщений: 32
	27.11.2023, 13:35
	Сообщение было отмечено RetykFlash как решение Решение Поиск самого длинного палиндрома к задаче не относится, по моему. Во-первых, () - не палниндром . Даже если адаптировать задачу так, чтобы () палиндромом считать, все равно (())() не является палиндромом. Решение за O(n) я, кажется, знаю, но не уверен, хотите вы решить сами или нет. 1