Задача : "Скобочки".

@turtLe · Регистрация: 11.11.2009

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

Некоторые скобочные структуры правильные, другие — неправильные. Ваша задача — определить правильная ли скобочная структура.

Вход: Слово в алфавите из двух круглых скобочек ( и ). Длина слова меньше 4001.

Выход: Либо 'NO', либо 'YES' без кавычек.

ВХОД #1:
()

ВЫХОД #1:
YES

ВХОД #2:
)(

ВЫХОД #2:
NO

ВХОД #3:
()(())()

ВЫХОД #3:
YES

http://acm.mipt.ru

Собственно вот мой код:

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
#include <string>
#include <iostream>
using namespace std;
 
int main()
{
    string str;
    bool b;
    int  k;
    b=true;
    cin>>str;
    k = str.length();
    if ((str.length() % 2 != 0) || (str[0] == ')')) b = false;
    while ( ( k > 0 ) && b )
    {
        if ( str[0] == '(' )
        {
            for (int j = 1; j < k ; j++)
                str[j-1] = str[j];
            k--;
            for (int j = 0; j < k ; j++)
                if ( str[j] == ')' ) 
                {
                    for (int t = j ; t < k - 1 ; t++) 
                        str[t] = str[t+1];
                    break;
                };
            k--;
        } else b = false;
    }
    if ( b == true ) cout<<"YES"; else cout<<"NO";
    return 0;
}

На одном из тестов моя программа выдает неверный результат, сам найти ошибку в своем алгоритме я пока не смог, прошу помощи в этом деле

@Mиxaил · 26.11.2011, 18:55

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

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
#include <iostream>
#include <string>
#include <stack>
 
int main()
{
    std::string s;
    std::cin >> s;
    std::stack < char > st;
    bool f = true;
    int index = 0;
 
    while ( index < s.length() && f )
    {
        if ( s [ index ] == ')' )
        {
            f = ( !st.empty() );
            if ( f )
                st.pop();
        }
        else
            st.push ( s [ index ] );
        index++;
    }
    std::cout << ( ( f && st.empty() ) ? "YES" : "NO" ) << std::endl;
}

На тестовых примерах проходит... Тестируйте!

P.S. Контестер это решение принял =)

valeriikozlov · 26.11.2011, 18:57

turtLe, Вот Вам в помощь тест:
()((

А задача решается намного проще:
- считали строку в str
- int k=0;
- потом проходите строку от начала до конца: если попалась скобка ( , то k++; если попалась скобка ) , то k--;
Если во время такого прохода k стало отрицательным, или по окончании не равно 0, то ответ NO, иначе YES

Байт · 26.11.2011, 19:01

C
1
2
3
4
5
6
7
for(s=0; *str!='/0'; str++) {
if (*str=='(') s++;
if (*str==')') s--;
if (s<0) break;
}
if (s==0) cout<< "YES";
else cout<<"NO";

Добавлено через 2 минуты
valeriikozlov,

Не по теме:

ну мы с вами прям как кошка с собакой:)

valeriikozlov · 26.11.2011, 19:03

Сообщение от Байт

Не по теме:
ну мы с вами прям как кошка с собакой

похоже

go · 26.11.2011, 19:06

Сообщение от Байт

for(s=0; *str!='/0'; str++) {

*str!='\0';
или
просто *str

Байт · 26.11.2011, 19:08

Сообщение от go

*str!='\0';
или
просто *str

Можно и так. Но я привык...

@Mиxaил · 26.11.2011, 19:08

valeriikozlov, можно еще упростить - просчитывать все на стадии заполнения, посимвольно!

go · 26.11.2011, 19:13

Сообщение от Байт

Можно и так. Но я привык...

А с чего вы взяли, что программа у вас не зациклится?

Байт · 26.11.2011, 19:18

Сообщение от go

А с чего вы взяли, что программа у вас не зациклится?

Если строка заканчивается нулем, то не должна...
А, простите, палка в другую сторону

C
1
for(s=0; *str!='\0'; str++) {

Добавлено через 50 секунд
Но это компилятор бы поймал

valeriikozlov · 26.11.2011, 19:20

Сообщение от Mиxaил

valeriikozlov, можно еще упростить - просчитывать все на стадии заполнения, посимвольно!

можно.

go · 26.11.2011, 19:37

Сообщение от Байт

Но это компилятор бы поймал

Нет, даже предупреждения не скажет

Байт · 26.11.2011, 19:49

Сообщение от go

Нет, даже предупреждения не скажет

Увы! Вы оказались правы!

@Liebe · 26.11.2011, 20:36

Сообщение от turtLe

На одном из тестов моя программа выдает неверный результат, сам найти ошибку в своем алгоритме я пока не смог, прошу помощи в этом деле

Ошибка в том, что алгоритмом не предусмотрен вариант строки, когда закрывающих скобок вообще нет. Например, "((((" - выдает "YES", а должен "NO".
Возможно, если исправить как ниже, то будет работать правильно. Но не факт. А лучше использовать выше предложенный алгоритм - он и по быстродействию лучше.

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
#include <string>
#include <iostream>
using namespace std;
 
int main()
{
        string str;
        bool b;
        int  k;
        b=true;
        cin>>str;
    k = str.length();
        if ((str.length() % 2 != 0) || (str[0] == ')')) b = false;
        while ( ( k > 0 ) && b )
        {
                if ( str[0] == '(' )
                {
                        for (int j = 1; j < k ; j++)
                                str[j-1] = str[j];
                        k--;
                        for ( int j = 0; j < k ; j++)
                                if ( str[j] == ')' ) 
                                {
                                        for (int t = j ; t < k - 1 ; t++) 
                         str[t] = str[t+1];
 
                    k--;//перенесли сюда, т.к. передвигаем влево, только когда условие верно
                        b=true;//так как пока со строкой все нормально
                    break;
                                }
                else b=false; //на случай если ни одной закрывающей скобки не встретится
                        //k--;
                } else b = false;
        }
        if ( b == true ) cout<<"YES"; else cout<<"NO";
    
        return 0;
}

@Nameless One · 26.11.2011, 21:10

Подытоживая вышесказанное:

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
#include <stdio.h>
#include <stdlib.h>
 
int main(int argc, char* argv[])
{
    int i, k;
 
    for(i = 1; i < argc; ++i)
    {
    printf("\"%s\": ", argv[i]);
    k = 0;
 
    while(*argv[i] != '\0')
    {
        k += (*argv[i] == '(' ? +1 :
          *argv[i] == ')' ? -1 : 0);
 
        if(k < 0)
        break;
 
        ++argv[i];
    }
 
    printf("%s\n", (k == 0 ? "YES" : "NO"));
    }
    
    exit(0);
}

Code
1
2
3
4
5
6
7
8
9
10
11
[nameless@desktop c]$ ./sample '((' '))' '(()((())))' '())' '()(' '()()(())' ')' ')(' '()'
"((": NO
"))": NO
"(()((())))": YES
"())": NO
"()(": NO
"()()(())": YES
")": NO
")(": NO
"()": YES
[nameless@desktop c]$

Сообщение от Mиxaил

попробуйте решать эту задачу, используя стек.

стек может быть полезен, если имеется несколько типов скобок

@Mиxaил · 26.11.2011, 21:16

Сообщение от Nameless One

стек может быть полезен, если имеется несколько типов скобок

Ага, я решал когда - то задачу с четырьмя видами скобок ( " ( { [ < " ), где нужно было добавить минимальное число скобок, чтобы получилось правильное скобочное выражение.

@turtLe · 27.11.2011, 08:22 **[ТС]**

Спасибо всем за Ваши ответы, разобрался

@meelvin182 · 02.10.2012, 22:14

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1000
 
int main(void)
{
    char stack[N], s[N];
    int stackid = 0, i;
    fgets(s, N - 1, stdin);
    for (i = 0; i < strlen(s); i++)
    {
        if (s[i] == '(' || s[i] == '[' || s[i]=='{')
        {
            stack[stackid] = s[i];
            stackid++;
            continue;
        }
        if (s[i] == ')' && stackid>0 && stack[stackid - 1] == '(')
        {
            stackid--;
            continue;
        }
        if (s[i] == ']' && stackid>0 && stack[stackid - 1] == '[')
        {
            stackid--;
            continue;
        }
        if (s[i] == '}' && stackid>0 && stack[stackid - 1] == '{')
        {
            stackid--;
            continue;
        }
        if (s[i]==']' || s[i]==')' || s[i]=='}')
        {
            stackid=-1;
            break;
        }
    }
    if (stackid == 0)
        printf("success\n");
    else
    {
        printf("error\n");
    }
    return EXIT_SUCCESS;
}

но это на Си и в более общем случае. Алгоритм решения тут просматривается.

@Nameless One · 03.10.2012, 00:53

meelvin182, поздравляю с удачным некропостом!

Сообщение от meelvin182

fgets(s, N - 1, stdin);

Почему N - 1, а не N?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

Задача : "Скобочки".

Решение

Решение

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	26.11.2011, 18:57
	Сообщение было отмечено как решение Решение turtLe, Вот Вам в помощь тест: ()(( А задача решается намного проще: - считали строку в str - int k=0; - потом проходите строку от начала до конца: если попалась скобка ( , то k++; если попалась скобка ) , то k--; Если во время такого прохода k стало отрицательным, или по окончании не равно 0, то ответ NO, иначе YES 6

@Mиxaил 542 / 447 / 162 Регистрация: 10.12.2009 Сообщений: 1,857
	26.11.2011, 19:08
	valeriikozlov, можно еще упростить - просчитывать все на стадии заполнения, посимвольно! 0

@turtLe 3 / 3 / 4 Регистрация: 11.11.2009 Сообщений: 41
	27.11.2011, 08:22 [ТС]
	Спасибо всем за Ваши ответы, разобрался 0