|
3 / 3 / 0
Регистрация: 05.10.2011
Сообщений: 86
|
|
Правильная скобочная последовательность01.10.2012, 09:15. Показов 49539. Ответов 8
Метки нет (Все метки)
Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа должна определить, является ли данная скобочная последовательность правильной.
Пустая последовательность является правильной. Если A – правильная, то последовательности (A), [A], {A} – правильные. Если A и B – правильные последовательности, то последовательность AB – правильная. Например. ([{}]) yes ([)] no ()() yes ())( no
0
|
|
| 01.10.2012, 09:15 | |
|
Ответы с готовыми решениями:
8
Правильная скобочная последовательность Правильная скобочная последовательность Правильная скобочная последовательность |
|
|
||||||
| 01.10.2012, 10:05 | ||||||
3
|
||||||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
| 01.10.2012, 14:19 | ||||||
|
igorrr37, аварийный выход при:
1
|
||||||
|
3 / 3 / 0
Регистрация: 05.10.2011
Сообщений: 86
|
|
| 07.10.2012, 06:45 [ТС] | |
|
igorrr37, спасибо огромное! кстати, с помощью этого метода решила еще несколько задач. спасибо.
valeriikozlov, и вам спасибо
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 07.10.2012, 06:56 | |
|
0
|
|
|
3 / 3 / 0
Регистрация: 05.10.2011
Сообщений: 86
|
|
| 08.10.2012, 22:37 [ТС] | |
|
valeriikozlov, просто он на java и немного запутанное условие задачи. но суть такая же. я решила сначала другим способом, но этот правильней, кажется.)
0
|
|
|
0 / 0 / 0
Регистрация: 10.11.2015
Сообщений: 1
|
||||||
| 10.11.2015, 14:19 | ||||||
|
А вообще, можно использовать стэк вызова, вот так:
0
|
||||||
|
29 / 27 / 2
Регистрация: 17.07.2019
Сообщений: 38
|
|
| 08.08.2021, 18:22 | |
|
Можно придумать наивный алгоритм проверки скобочной последовательности на правильность. В правильной скобочной последовательности всегда есть пара скобок, внутри которой нет других скобок. Это пара из открывающей и закрывающей скобки одного вида, идущих рядом. Удалим их. Опять найдём такую пару и снова удалим. Будем продолжать этот процесс, пока есть такие пары. Если мы в итоге смогли удалить все скобки, то есть все скобки разбились на пары открывающих и закрывающих, то последовательность правильная. Если же на каком-то шаге мы не смогли найти пару соседних подходящих скобок, но скобки ещё остались, то последовательность неправильная.
Но такой алгоритм при наивной реализации будет иметь сложность O(n2). Действительно, давайте рассмотрим последовательность, в которой сначала идут n/2 открывающих скобок одного типа, потом n/2 закрывающих скобок того же типа. Эта последовательность будет правильной. Но каждый раз мы будем удалять две скобки из середины нашей строки, что будет выполняться за O(n), поскольку необходимо сдвигать половину элементов строки. Это удаление элементов из середины будет выполняться n/2 раз, поэтому общая сложность будет O(n2). Можно улучшить этот алгоритм, если использовать стек. Закрывающая скобка должна быть парной к последней открывающей. То есть если мы будем хранить последовательность из открывающих скобок, то закрывающая скобка удаляет последнюю открывающую, если она того же вида, в противном случае скобочная последовательность неправильная. Это означает, что последовательность открывающих скобок, которые не были ещё закрыты, представляет собой стек. Если мы встретили открывающую скобку, то она добавляется в конец стека. Если мы встретили закрывающую скобку, то должны выполняться следующие условия: стек не пуст и на вершине стека хранится скобка, парная данной закрывающей скобке. Если после обработки всех скобок стек оказался пуст, то последовательность правильная. В каком случае последовательность будет неправильной? Если для очередной закрывающей скобки не нашлось парной открывающей, то есть если мы встретили закрывающую скобку, то либо стек пуст, либо на вершине его находится скобка другого вида. Или если мы для какой-то открывающей скобки не нашли закрывающую, это означает, что после рассмотрения всех скобок стек оказался не пуст. Сложность алгоритма O(n), так как каждую скобку мы кладём в стек или удаляем из стека не более одного раза, а данные операции на стеке работают за O(1).
0
|
|
|
1 / 1 / 0
Регистрация: 17.11.2023
Сообщений: 8
|
||||||
| 25.11.2023, 14:02 | ||||||
|
код который прошёл все проверки Сириуса:
0
|
||||||
| 25.11.2023, 14:02 | |
|
Помогаю со студенческими работами здесь
9
Проверка записи на соответствие условию: правильная скобочная запись из круглых и квадратных скобок Скобочная последовательность
Правильная скобковая последовательность, почему дублируется последний ответ?
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта
Симптом:
После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
|
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
|
Новый ноутбук
volvo 07.12.2025
Всем привет.
По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне:
Ryzen 5 7533HS
64 Gb DDR5
1Tb NVMe
16" Full HD Display
Win11 Pro
|
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
|
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
|
|
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов
На странице:
https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/
нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
|
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
|
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
|
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут.
В век Веб все очень привыкли к дизайну Single-Page-Application .
Быстренько разберем подход "на фреймах".
Мы делаем одну. . .
|