Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.72/254: Рейтинг темы: голосов - 254, средняя оценка - 4.72
 Аватар для Ann Joker
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
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
01.10.2012, 09:15
Ответы с готовыми решениями:

Правильная скобочная последовательность
Напомним, что называется правильной скобочной последовательностью: пустая строка является правильной скобочной последовательностью; ...

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

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

8
 Аватар для igorrr37
2869 / 2016 / 991
Регистрация: 21.12.2010
Сообщений: 3,721
Записей в блоге: 15
01.10.2012, 10:05
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
#include <iostream>
#include <stack>
#include <string>
 
inline bool LeftBracket(char c)
{
    return ('(' == c || '{' == c || '[' == c);
}
 
inline bool Fit(char lb, char rb)
{
    return ('(' == lb && ')' == rb) || ('[' == lb && ']' == rb) || ('{' == lb && '}' == rb);
}
 
int main()
{
    std::string s = "(][)";
    std::stack<char> stack;
    for(std::string::const_iterator it(s.begin()), itEnd(s.end()); it != itEnd; ++it)
    {
        if(LeftBracket(*it))
        {
            stack.push(*it);
        }
        else if(Fit(stack.top(), *it))
        {
            stack.pop();
        }
        else
        {
            stack.push(*it);
            break;
        }
    }
    std::cout << (stack.empty() ? "right" : "wrong") << std::endl;
    return 0;
}
3
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
01.10.2012, 14:19
igorrr37, аварийный выход при:
C++
1
std::string s = ")";
1
 Аватар для Ann Joker
3 / 3 / 0
Регистрация: 05.10.2011
Сообщений: 86
07.10.2012, 06:45  [ТС]
igorrr37, спасибо огромное! кстати, с помощью этого метода решила еще несколько задач. спасибо.
valeriikozlov, и вам спасибо
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
07.10.2012, 06:56
Цитата Сообщение от Ann Joker Посмотреть сообщение
кстати, с помощью этого метода решила еще несколько задач.
если не жалко, покажите код к этой задаче, который получился )
0
 Аватар для Ann Joker
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
А вообще, можно использовать стэк вызова, вот так:

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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int sz = 1;
 
bool check(char v)
{
    char t;
    scanf("%c", &t);
    if(t == EOF || t == '\n' || t == 0)
    {
        return (!sz ? true : false);
    }
 
    if(t == ')')
    {
        if(v == '(')
        {
            sz--;
            return true;
        }
        return false;
    }
 
    if(t == '}')
    {
        if(v == '{')
        {
            sz--;
            return true;
        }
        return false;
    }
 
    if(t == ']')
    {
        if(v == ']')
        {
            sz--;
            return false;
        }
        return true;
    }
 
    if(t == '{' || t == '[' || t == '(')
    {
        sz++;
        if(check(t))
            return check(v);
        else
            return false;
    }
 
    return check(v);
}
 
int main()
{
    char t;
    scanf("%c", &t);
 
    while(t != EOF && t != '\n' && t != 0)
    {
        if(!check(t))
        {
            cout << "no" << endl;
            return 0;
        }
        scanf("%c", &t);
    }
 
    cout << "yes" << endl;
    return 0;
}
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
код который прошёл все проверки Сириуса:
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
#include <iostream>
#include <stack>
using namespace std;
 
bool is_correct_brackets(string expr) {
    stack<char> st;
    for (char c : expr) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) {
                return false;
            }
            char current_char = st.top();
            st.pop();
            if (current_char == '(') {
                if (c != ')') {
                    return false;
                }
            }
            if (current_char == '{') {
                if (c != '}') {
                    return false;
                }
            }
            if (current_char == '[') {
                if (c != ']') {
                    return false;
                }
            }
        }
    }
    if (!st.empty()) {
        return false;
    }
    return true;
}
 
int main() {
    string a;
    cin >> a;
    if (is_correct_brackets(a)) {
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
25.11.2023, 14:02
Помогаю со студенческими работами здесь

Проверка записи на соответствие условию: правильная скобочная запись из круглых и квадратных скобок
Здравствуйте! Задача: проверка записи на соответствие условию: правильная скобочная запись из круглых и квадратных скобок, внутри...

Скобочная последовательность
Нужно ввести имя файла из консоли, в котором будет находиться какая-то скобочная последовательность. И затем в консоле выводит правильная...

Скобочная последовательность
Написать алгоритм перечисления правильных скобочных последовательностей длины n в лексикографическом порядке. Подсказка: Первая...

Правильная скобковая последовательность, почему дублируется последний ответ?
#include &lt;iostream&gt; #include &lt;string&gt; #include &lt;fstream&gt; #include &lt;stack&gt; using namespace std; int main() { ifstream in; ...

Правильная последовательность флага IOPL в регистре EFLAGS
Добрый день! Разбираю регистр EFLAGS в контексте потока (CONTEXT::EFlags) CONTEXT ThreadContext = { 0 }; ...


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

Или воспользуйтесь поиском по форуму:
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 . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru