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

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

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

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

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

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

ВХОД #1:
()

ВЫХОД #1:
YES

ВХОД #2:
)(

ВЫХОД #2:
NO

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

ВЫХОД #3:
YES

http://acm.mipt.ru

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

C++

#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++

#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

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++

#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

#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ил · 26.11.2011, 21:16

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

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

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

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

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

@meelvin182 · 02.10.2012, 22:14

C

#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?

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

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

Решение

Решение

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

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	26.11.2011, 19:03	5
	Сообщение от Байт Не по теме: ну мы с вами прям как кошка с собакой похоже 0

go 3646 / 1378 / 243 Регистрация: 16.04.2009 Сообщений: 4,526
	26.11.2011, 19:06	6
	Сообщение от Байт for(s=0; str!='/0'; str++) { str!='\0'; или просто *str 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	26.11.2011, 19:08	7
	Сообщение от go str!='\0'; или просто str Можно и так. Но я привык... 0

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

go 3646 / 1378 / 243 Регистрация: 16.04.2009 Сообщений: 4,526
	26.11.2011, 19:13	9
	Сообщение от Байт Можно и так. Но я привык... А с чего вы взяли, что программа у вас не зациклится? 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	26.11.2011, 19:20	11
	Сообщение от Mиxaил valeriikozlov, можно еще упростить - просчитывать все на стадии заполнения, посимвольно! можно. 0

go 3646 / 1378 / 243 Регистрация: 16.04.2009 Сообщений: 4,526
	26.11.2011, 19:37	12
	Сообщение от Байт Но это компилятор бы поймал Нет, даже предупреждения не скажет 2

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	26.11.2011, 19:49	13
	Сообщение от go Нет, даже предупреждения не скажет Увы! Вы оказались правы! 0

@Mиxaил 542 / 447 / 162 Регистрация: 10.12.2009 Сообщений: 1,857
	26.11.2011, 21:16	16
	Сообщение от Nameless One стек может быть полезен, если имеется несколько типов скобок Ага, я решал когда - то задачу с четырьмя видами скобок ( " ( { [ < " ), где нужно было добавить минимальное число скобок, чтобы получилось правильное скобочное выражение. 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	03.10.2012, 00:53	19
	meelvin182, поздравляю с удачным некропостом! Сообщение от meelvin182 fgets(s, N - 1, stdin); Почему N - 1, а не N? 0