Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/47: Рейтинг темы: голосов - 47, средняя оценка - 4.83
0 / 0 / 0
Регистрация: 27.03.2020
Сообщений: 37
1

Удаление скобок

03.12.2020, 17:35. Показов 8734. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Дана строка, составленная из круглых, квадратных и фигурных скобок. Определите, какое наименьшее количество символов необходимо удалить из этой строки, чтобы оставшиеся символы образовывали правильную скобочную последовательность.

Формат ввода
Во входном файле записана строка из круглых, квадратных и фигурных скобок. Длина строки не превосходит 100 символов.

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

Пример 1
Ввод Вывод
([)] - []
Пример 2
Ввод Вывод
{([(]{)})] - [({})]
Пример 3
Ввод Вывод
]{)[ -



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
#include <algorithm>
 
using namespace std;
 
int dp[101][101];
 
char inv(char c)
{
    if (c == ')') return '(';
    if (c == ']') return '[';
    if (c == '}') return '{';
    return '-';
}
 
bool open(char c)
{
    if (c == '{' || c == '(' || c == '[') return true;
    return false;
}
 
int main() {
    string s;
    vector<vector<string>> ans(101, vector<string>(101, ""));
    cin >> s;
    int n = s.length();
    for (int i = 0; i < n; ++i) dp[i][i] = 0;
    for (int i = n - 1; i >= 0; --i)
    {
        for (int j = i + 2; j < n; ++j)
        {
            if (s[i] == inv(s[j]) && open(s[i]))
            {
                ans[i][j] = s[i] + ans[i + 1][j - 1] + s[j];
                dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
            }else
            {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                if (dp[i][j] == dp[i + 1][j]) ans[i][j] = ans[i + 1][j];
                else ans[i][j] = ans[i][j - 1];
            }
        }
    }
    cout << ans[0][n - 1];
}
Задача - вывести правильную скобочную последовательность. Я восстановлял ответ с помощью еще одной динамики. Прошло всего лишь пять тестов. Где проблема? Или дело в том, что выведенная скобочная последовательность всегда должна быть отсортирована. Типо: [[[[[(((())))]]]]], а не как в самой строке?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.12.2020, 17:35
Ответы с готовыми решениями:

Функция: удаление текста внутри скобок вместе со скобками
Использую MS VS2017 , закомментируйте пожалуйста данную функцию (char* str_remove(char* s, char a,...

Вывести все корректные комбинации пар круглых скобок, которые можно сформировать из n скобок
Вывести все корректные комбинации пар круглых скобок, которые можно сформировать из n скобок,...

Удаление скобок
Здравствуйте! помогите написать макрос, который будет в определенном столбце удалять скобки вместе...

Удаление лишних скобок
С#. Пользователь вводит строку символов. состоящую из букв латинского алфавита и скобок {} (),...

1
392 / 262 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
03.12.2020, 18:20 2
Скобки
0
03.12.2020, 18:20
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.12.2020, 18:20
Помогаю со студенческими работами здесь

Удаление попарных скобок
В заданном предложении удалить фигурные и квадратные скобки, если они встречаются попарно ( ‘’,...

Удаление скобок из строки
Решаю задания на freeCodeCamp столкнулся с такой вот задачей. Нужно проверить является ли строка...

Строки. Удаление скобок.
С клавиатуры вводится строка выражения/текста. Удалить из заданной строки фрагменты, заключенные в...

Удаление скобок в логическом выражении
Здравствуйте. Задание: удалить лишние скобки в логическом выражении. Есть код на Pascal uses...

Удаление непарных скобок в строке
Здравствуйте, форумчане! Требуется помощь в написании программы. Есть строка, в которой содержатся...

Удаление в не круглых скобок и их сами
Пользователь вводит строку. Составить из неее строку из символов, находящихся между между парами...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru