Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
turtLe
3 / 3 / 2
Регистрация: 11.11.2009
Сообщений: 41
#1

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

26.11.2011, 18:37. Просмотров 1636. Ответов 18
Метки нет (Все метки)

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

Вход: Слово в алфавите из двух круглых скобочек ( и ). Длина слова меньше 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;
}
На одном из тестов моя программа выдает неверный результат, сам найти ошибку в своем алгоритме я пока не смог, прошу помощи в этом деле
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2011, 18:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача : "Скобочки". (C++):

Даны три слова - "мама", "мыла", "раму". Задача - напечатать всевозможные варианты построения слов - C++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include &lt;iostream&gt; using namespace std; int main()...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64" - C++
доброго времени суток. Необработанное исключение в &quot;0x76f015de&quot; в &quot;контрольная 1 задача 2.exe&quot;: 0xC0000005: Нарушение прав доступа при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

18
Mиxaил
533 / 438 / 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. Контестер это решение принял =)
0
valeriikozlov
Эксперт С++
4672 / 2498 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.11.2011, 18:57 #3
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
turtLe, Вот Вам в помощь тест:
()((

А задача решается намного проще:
- считали строку в str
- int k=0;
- потом проходите строку от начала до конца: если попалась скобка ( , то k++; если попалась скобка ) , то k--;
Если во время такого прохода k стало отрицательным, или по окончании не равно 0, то ответ NO, иначе YES
6
Байт
Эксперт C
16535 / 10805 / 1638
Регистрация: 24.12.2010
Сообщений: 20,827
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,

Не по теме:

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

4
valeriikozlov
Эксперт С++
4672 / 2498 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.11.2011, 19:03 #5
Цитата Сообщение от Байт Посмотреть сообщение
Не по теме:
ну мы с вами прям как кошка с собакой
похоже
0
go
Эксперт С++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
26.11.2011, 19:06 #6
Цитата Сообщение от Байт Посмотреть сообщение
for(s=0; *str!='/0'; str++) {
*str!='\0';
или
просто *str
0
Байт
Эксперт C
16535 / 10805 / 1638
Регистрация: 24.12.2010
Сообщений: 20,827
26.11.2011, 19:08 #7
Цитата Сообщение от go Посмотреть сообщение
*str!='\0';
или
просто *str
Можно и так. Но я привык...
0
Mиxaил
533 / 438 / 37
Регистрация: 10.12.2009
Сообщений: 1,857
26.11.2011, 19:08 #8
valeriikozlov, можно еще упростить - просчитывать все на стадии заполнения, посимвольно!
0
go
Эксперт С++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
26.11.2011, 19:13 #9
Цитата Сообщение от Байт Посмотреть сообщение
Можно и так. Но я привык...
А с чего вы взяли, что программа у вас не зациклится?
0
Байт
Эксперт C
16535 / 10805 / 1638
Регистрация: 24.12.2010
Сообщений: 20,827
26.11.2011, 19:18 #10
Цитата Сообщение от go Посмотреть сообщение
А с чего вы взяли, что программа у вас не зациклится?
Если строка заканчивается нулем, то не должна...
А, простите, палка в другую сторону
C
1
for(s=0; *str!='\0'; str++) {
Добавлено через 50 секунд
Но это компилятор бы поймал
0
valeriikozlov
Эксперт С++
4672 / 2498 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.11.2011, 19:20 #11
Цитата Сообщение от Mиxaил Посмотреть сообщение
valeriikozlov, можно еще упростить - просчитывать все на стадии заполнения, посимвольно!
можно.
0
go
Эксперт С++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
26.11.2011, 19:37 #12
Цитата Сообщение от Байт Посмотреть сообщение
Но это компилятор бы поймал
Нет, даже предупреждения не скажет
2
Байт
Эксперт C
16535 / 10805 / 1638
Регистрация: 24.12.2010
Сообщений: 20,827
26.11.2011, 19:49 #13
Цитата Сообщение от go Посмотреть сообщение
Нет, даже предупреждения не скажет
Увы! Вы оказались правы!
0
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;
}
1
Nameless One
Эксперт С++
5775 / 3425 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
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ил Посмотреть сообщение
попробуйте решать эту задачу, используя стек.
стек может быть полезен, если имеется несколько типов скобок
1
26.11.2011, 21:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.11.2011, 21:10
Привет! Вот еще темы с ответами:

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...

Структура «Преподаватель» с полями "ФИО", "стаж", "категория", "нагрузка" - C++
Функция - расчёт зарплаты по нагрузке и оплате часа для определенной категории. Категория Оплата часа Вторая 150 Первая 200 ...

по строкам.замените в слове сочетание "му" на "а" , а букву "ы" на "ца". очень нужно - C++
замените в слове сочетание &quot;му&quot; на &quot;а&quot; , а букву &quot;ы&quot; на &quot;ца&quot;. очень нужно Добавлено через 21 час 4 минуты неужели никто не знает...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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