Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 35, средняя оценка - 4.86
Ann Joker
3 / 3 / 1
Регистрация: 05.10.2011
Сообщений: 86
#1

Правильная скобочная последовательность - C++

01.10.2012, 09:15. Просмотров 4929. Ответов 6
Метки нет (Все метки)

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

Пустая последовательность является правильной. Если A – правильная, то последовательности (A), [A], {A} – правильные. Если A и B – правильные последовательности, то последовательность AB – правильная.

Например.
([{}]) yes
([)] no
()() yes
())( no
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.10.2012, 09:15     Правильная скобочная последовательность
Посмотрите здесь:

Вводится последовательность из N целых чисел. Сформировать последовательность, C++
C++ Дана последовательность, элементы которой есть целые двузначные числа. Упорядочить последовательность по убыванию произведений цифр
Массив: Вставить в последовательность действительное число b так, чтобы последовательность осталась неубывающей. C++
C++ Правильная инициализация ?
Проверка записи на соответствие условию: правильная скобочная запись из круглых и квадратных скобок C++
C++ Правильная ли программа?
Правильная скобочная последовательность C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
igorrr37
1618 / 1246 / 124
Регистрация: 21.12.2010
Сообщений: 1,903
Записей в блоге: 7
01.10.2012, 10:05     Правильная скобочная последовательность #2
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;
}
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
01.10.2012, 14:19     Правильная скобочная последовательность #3
igorrr37, аварийный выход при:
C++
1
std::string s = ")";
Ann Joker
3 / 3 / 1
Регистрация: 05.10.2011
Сообщений: 86
07.10.2012, 06:45  [ТС]     Правильная скобочная последовательность #4
igorrr37, спасибо огромное! кстати, с помощью этого метода решила еще несколько задач. спасибо.
valeriikozlov, и вам спасибо
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.10.2012, 06:56     Правильная скобочная последовательность #5
Цитата Сообщение от Ann Joker Посмотреть сообщение
кстати, с помощью этого метода решила еще несколько задач.
если не жалко, покажите код к этой задаче, который получился )
Ann Joker
3 / 3 / 1
Регистрация: 05.10.2011
Сообщений: 86
08.10.2012, 22:37  [ТС]     Правильная скобочная последовательность #6
valeriikozlov, просто он на java и немного запутанное условие задачи. но суть такая же. я решила сначала другим способом, но этот правильней, кажется.)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.11.2015, 14:19     Правильная скобочная последовательность
Еще ссылки по теме:

Если последовательность отсортирована по возрастанию, оставить ее без изменения. Иначе получить иную последовательность C++
C++ Вводится последовательность из N вещественных чисел. Определить, является ли последовательность знакочередующе
Скобочная последовательность C++
Правильная скобочная последовательность C++
C++ Правильная компиляция

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

Или воспользуйтесь поиском по форуму:
O4koZaO4ko
0 / 0 / 0
Регистрация: 10.11.2015
Сообщений: 1
10.11.2015, 14:19     Правильная скобочная последовательность #7
А вообще, можно использовать стэк вызова, вот так:

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;
}
Yandex
Объявления
10.11.2015, 14:19     Правильная скобочная последовательность
Ответ Создать тему
Опции темы

Текущее время: 19:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru