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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
turtLe
3 / 3 / 2
Регистрация: 11.11.2009
Сообщений: 41
26.11.2011, 18:37     Задача : "Скобочки". #1
Некоторые скобочные структуры правильные, другие — неправильные. Ваша задача — определить правильная ли скобочная структура.

Вход: Слово в алфавите из двух круглых скобочек ( и ). Длина слова меньше 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ил
 Аватар для Mиxaил
530 / 435 / 37
Регистрация: 10.12.2009
Сообщений: 1,857
26.11.2011, 18:55     Задача : "Скобочки". #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
#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
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.11.2011, 18:57     Задача : "Скобочки". #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
turtLe, Вот Вам в помощь тест:
()((

А задача решается намного проще:
- считали строку в str
- int k=0;
- потом проходите строку от начала до конца: если попалась скобка ( , то k++; если попалась скобка ) , то k--;
Если во время такого прохода k стало отрицательным, или по окончании не равно 0, то ответ NO, иначе YES
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,930
26.11.2011, 19:01     Задача : "Скобочки". #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.11.2011, 19:03     Задача : "Скобочки". #5
Цитата Сообщение от Байт Посмотреть сообщение
Не по теме:
ну мы с вами прям как кошка с собакой
похоже
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
26.11.2011, 19:06     Задача : "Скобочки". #6
Цитата Сообщение от Байт Посмотреть сообщение
for(s=0; *str!='/0'; str++) {
*str!='\0';
или
просто *str
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,930
26.11.2011, 19:08     Задача : "Скобочки". #7
Цитата Сообщение от go Посмотреть сообщение
*str!='\0';
или
просто *str
Можно и так. Но я привык...
Mиxaил
 Аватар для Mиxaил
530 / 435 / 37
Регистрация: 10.12.2009
Сообщений: 1,857
26.11.2011, 19:08     Задача : "Скобочки". #8
valeriikozlov, можно еще упростить - просчитывать все на стадии заполнения, посимвольно!
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
26.11.2011, 19:13     Задача : "Скобочки". #9
Цитата Сообщение от Байт Посмотреть сообщение
Можно и так. Но я привык...
А с чего вы взяли, что программа у вас не зациклится?
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,930
26.11.2011, 19:18     Задача : "Скобочки". #10
Цитата Сообщение от go Посмотреть сообщение
А с чего вы взяли, что программа у вас не зациклится?
Если строка заканчивается нулем, то не должна...
А, простите, палка в другую сторону
C
1
for(s=0; *str!='\0'; str++) {
Добавлено через 50 секунд
Но это компилятор бы поймал
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.11.2011, 19:20     Задача : "Скобочки". #11
Цитата Сообщение от Mиxaил Посмотреть сообщение
valeriikozlov, можно еще упростить - просчитывать все на стадии заполнения, посимвольно!
можно.
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
26.11.2011, 19:37     Задача : "Скобочки". #12
Цитата Сообщение от Байт Посмотреть сообщение
Но это компилятор бы поймал
Нет, даже предупреждения не скажет
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,930
26.11.2011, 19:49     Задача : "Скобочки". #13
Цитата Сообщение от go Посмотреть сообщение
Нет, даже предупреждения не скажет
Увы! Вы оказались правы!
Liebe
...
 Аватар для Liebe
891 / 74 / 5
Регистрация: 21.02.2010
Сообщений: 2,196
Записей в блоге: 1
26.11.2011, 20:36     Задача : "Скобочки". #14
Цитата Сообщение от 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
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
26.11.2011, 21:10     Задача : "Скобочки". #15
Подытоживая вышесказанное:
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);
}
Код
[nameless@desktop c]$ ./sample '((' '))' '(()((())))' '())' '()(' '()()(())' ')' ')(' '()'
"((": NO
"))": NO
"(()((())))": YES
"())": NO
"()(": NO
"()()(())": YES
")": NO
")(": NO
"()": YES
[nameless@desktop c]$
Цитата Сообщение от Mиxaил Посмотреть сообщение
попробуйте решать эту задачу, используя стек.
стек может быть полезен, если имеется несколько типов скобок
Mиxaил
 Аватар для Mиxaил
530 / 435 / 37
Регистрация: 10.12.2009
Сообщений: 1,857
26.11.2011, 21:16     Задача : "Скобочки". #16
Цитата Сообщение от Nameless One Посмотреть сообщение
стек может быть полезен, если имеется несколько типов скобок
Ага, я решал когда - то задачу с четырьмя видами скобок ( " ( { [ < " ), где нужно было добавить минимальное число скобок, чтобы получилось правильное скобочное выражение.
turtLe
3 / 3 / 2
Регистрация: 11.11.2009
Сообщений: 41
27.11.2011, 08:22  [ТС]     Задача : "Скобочки". #17
Спасибо всем за Ваши ответы, разобрался
meelvin182
1 / 1 / 0
Регистрация: 02.09.2012
Сообщений: 15
02.10.2012, 22:14     Задача : "Скобочки". #18
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;
}
но это на Си и в более общем случае. Алгоритм решения тут просматривается.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.10.2012, 00:53     Задача : "Скобочки".
Еще ссылки по теме:

Задача "Кто старше?" (подскажите где ошибка в коде) C++
Задача "Гигабашня": минимальное расстояние до этажа со счастливым номером C++
C++ Переменные "емкость", "Галлон", "Бензин"

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

Или воспользуйтесь поиском по форуму:
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
03.10.2012, 00:53     Задача : "Скобочки". #19
meelvin182, поздравляю с удачным некропостом!

Цитата Сообщение от meelvin182 Посмотреть сообщение
fgets(s, N - 1, stdin);
Почему N - 1, а не N?
Yandex
Объявления
03.10.2012, 00:53     Задача : "Скобочки".
Ответ Создать тему
Опции темы

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