Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [С++] Баланс скобок с строке 
V
    Опции темы
katz
Дата 26.1.2007, 21:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 8
Регистрация: 16.1.2007

Репутация: нет
Всего: нет
Привет. Такая вот задача. Проверить наличие баланса скобок в файле.
PM MAIL   Вверх
Xenon
Дата 26.1.2007, 21:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 19
Всего: 50
katz, Баланс скобок?


--------------------
user posted image  
PM MAIL   Вверх
Данкинг
Дата 26.1.2007, 21:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Yersinia pestis
****


Профиль
Группа: Завсегдатай
Сообщений: 8302
Регистрация: 7.11.2006
Где: მოსკოვი

Репутация: нет
Всего: 130
Это типа число открывающих равно числу закрывающих? Если так - то и мне покажите, как это сделать в качестве урока работы с файлами и строками на С++ ! smile 


--------------------
There's nothing left but silent epitaphs.
PM MAIL WWW   Вверх
Sartorius
Дата 26.1.2007, 22:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37
 Вот тебе баланс скобок в строке (на файл сам перенесешь)
Код

int i = 0;
char str[] = "bla bla bla";
for(int j = 0; j < strlen(str); j++)
{
   if(str[j] == ')') i--;
   if(str[j] == '("') i++;
   if(i < 0)
   {
      cout << "Ахтунг, нарушен порядок скобок";
      return -1;
    }
}

if(i !=0)
{
   cout << "Alarm, баланс скобок нарушен";
}
}
PM MAIL ICQ   Вверх
zkv
Дата 26.1.2007, 22:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92
я тоже попробую smile
Код

#include <iostream>
#include <fstream>
#include <iterator>

using namespace std;

bool ValidateBrackets( const char *pcFileName );

int main(int argc, char* argv[])
{
        if( ValidateBrackets( "input.txt" ) )
            cout<<"All right";
        else
            cout<<"Very bad";
        cin.get();
}
bool ValidateBrackets( const char *pcFileName )
{
    ifstream fin( pcFileName );
    int iNumOpenBrackets = 0;
    
    for( istream_iterator<char> itFIn(fin); 
         itFIn != istream_iterator<char>(); 
         ++itFIn )
    {
        if( *itFIn == '(' )
            ++iNumOpenBrackets;
        else if( *itFIn == ')' )
            if( !iNumOpenBrackets )
                return false;
            else 
                --iNumOpenBrackets;
    }
    return static_cast<bool>(!iNumOpenBrackets);
}


Это сообщение отредактировал(а) zkv - 26.1.2007, 22:35
PM MAIL   Вверх
Данкинг
Дата 26.1.2007, 23:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Yersinia pestis
****


Профиль
Группа: Завсегдатай
Сообщений: 8302
Регистрация: 7.11.2006
Где: მოსკოვი

Репутация: нет
Всего: 130
Первую понял, во второй операторы незнакомые покамест...


--------------------
There's nothing left but silent epitaphs.
PM MAIL WWW   Вверх
Oleg_Ci
Дата 27.1.2007, 07:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Friend
**


Профиль
Группа: Участник
Сообщений: 485
Регистрация: 28.5.2006
Где: Новосиб.обл.

Репутация: 25
Всего: 30
Всё-таки, под балансом что надо понимать ?
1) (()) - здесь ясно - баланс есть.
2) ))(( - а так? smile  не одной "собранной"
т.е. строка ведь должна открываться '(' а потом закрыватся ')'.
у меня второй пример за баланс несчитается.
Код

#include <iostream>
#include <fstream>
using std::cout;
using std::cin;
using std::ifstream;

bool balans( const char * filename = "text.txt" ); // проверка баланса

////////////// MAIN ////////////////////
int main()
{
    if( balans())
        cout << "Ok !\n";
    else cout << "Error balans !\n";

    cin.get(); // пауза
    return 0;
}
/////////////// End main //////////////////

bool balans( const char * filename ){
    ifstream file( filename ); // открываем файл
    if( !file.is_open()){ // если неоткрывается
        cout << "Error open file " << filename << "\n";
        cin.get(); // пауза
        exit(1);
    }
    int bracket = 0;
    char c;
    while( file.get(c)){
        switch (c){
            case '(': bracket++; break;
            case ')': bracket--; break;
            default: break;
        }
        if( bracket < 0 ) // если закрытых скобок больше то баланс нарушен!
            return false;
    }
    if( bracket )
        return false;
    else return true;
}


Это сообщение отредактировал(а) Oleg_Ci - 27.1.2007, 07:35
PM MAIL   Вверх
Oleg_Ci
Дата 27.1.2007, 07:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Friend
**


Профиль
Группа: Участник
Сообщений: 485
Регистрация: 28.5.2006
Где: Новосиб.обл.

Репутация: 25
Всего: 30
У zkv, принцып такой-же, второй вариант ошибочный.
Я имею ввиду этот - 
Цитата
2) ))(( - а так?   не одной "собранной"


Это сообщение отредактировал(а) Oleg_Ci - 27.1.2007, 07:39
PM MAIL   Вверх
Kuvaldis
Дата 27.1.2007, 14:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
Модератор: Название темы должно отражать ее суть!


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
V.A.KeRneL
  Дата 28.1.2007, 11:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Vadim A. Kazantsev
**


Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: 7
Всего: 14
Цитата(Kuvaldis @  27.1.2007, 14:57 Найти цитируемый пост)

Модератор: Название темы должно отражать ее суть!

ИМХО, содержит. «Баланс скобок» — общепринятый термин. И то что многие здесь его не знают, не отменяет этого. Аффтар katz не виноват! smile



--------------------
«C'est un pense-creux d'ici. C'est le meilleur et le plus irascible homme du monde...» © Ф.М. Достоевский, «Бесы»
---/)/)---(\.../)---(\(\
--(':'=)---(=';'=)---(=':')
(")(")..)-(").--.(")-(..(")(")
PM MAIL IM ICQ AOL YIM MSN   Вверх
zkv
Дата 28.1.2007, 14:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92
оффтоп - восстановление справедливости smile
Цитата(V.A.KeRneL @  28.1.2007,  11:37 Найти цитируемый пост)
ИМХО, содержит. «Баланс скобок» — общепринятый термин. И то что многие здесь его не знают, не отменяет этого. Аффтар katz не виноват! smile

просто на момент написания сего замечания:
Цитата

Модератор: Название темы должно отражать ее суть! 

тема называлась "[c++]"

Это сообщение отредактировал(а) zkv - 28.1.2007, 14:13
PM MAIL   Вверх
V.A.KeRneL
  Дата 28.1.2007, 19:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Vadim A. Kazantsev
**


Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: 7
Всего: 14
Хотя нет, я погорячился. 
katz виноват... в том, что до сих пор не пометил задачу решённой! 
(Просто даже передать не могу, как меня это раздражает!)


Это сообщение отредактировал(а) V.A.KeRneL - 28.1.2007, 19:39


--------------------
«C'est un pense-creux d'ici. C'est le meilleur et le plus irascible homme du monde...» © Ф.М. Достоевский, «Бесы»
---/)/)---(\.../)---(\(\
--(':'=)---(=';'=)---(=':')
(")(")..)-(").--.(")-(..(")(")
PM MAIL IM ICQ AOL YIM MSN   Вверх
Akeem
Дата 28.1.2007, 20:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 14.7.2006
Где: Киев/Украина

Репутация: 1
Всего: 3
один только момент это задача из теори алгоритмов и тут просится чтобы в сроке находились баланс скобок вида ({[]()})


тогда алгоритм  немного усложнен.


--------------------
Мир огромен и мы только муравьи в нём! (С) formicha
PM MAIL WWW ICQ   Вверх
V.A.KeRneL
Дата 28.1.2007, 20:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Vadim A. Kazantsev
**


Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: 7
Всего: 14
Ах, да, Akeem, действительно, возможно это имелось в виду. Но в любом случае katz'у следовало более подробно обрисовать ситуацию.

Вот, как раз, решил в прошедшем семестре эту задачку. 
brackets.c: 
Код

/* brackets
   
   Copyright (C) 2006 Vadim A. Kazantsev aka V.A.KeRneL.
 */

#include <stdio.h>
/*#include <stdio_ext.h>*/
//#include <stdlib.h>
//#include <malloc.h>
//#include <string.h>

/* ************************************************************************ */

#if defined( VERBOSE )
#    define Vprintf( args )    printf args
#    define Vputchar( args )   putchar args
#else
#    define Vprintf( args )    /* empty */
#    define Vputchar( args )   /* empty */
#endif

/* ************************************************************************ */

/**/
#define TRUE   1
#define FALSE  0
typedef int bool;
/**/

/*
enum _bool { 
    FALSE = 0;
#define FALSE FALSE
    TRUE  = 1;
#define TRUE  TRUE
};

typedef   struct _bool   bool;
#define bool bool
*/

/* ************************************************************************ */

#define STACK_SIZE 1000  /* (may be changed) */

typedef struct { 
    int s[ STACK_SIZE + 1 ];  /* body of stack */
    //int t[ STACK_SIZE + 1 ];  /* type of element */
    int top;                  /* position of higher element */
    int count;                /* number of stack element */
} stack;

stack ss;

int last_elem;
//int last_type;

void init_stack( stack * s );
void push( stack * s, int x /*, int type*/ );
int  pop( stack * s );
bool /*int*/ is_empty( stack * s );

void 
init_stack( stack * s ) 
{ 
    s->top = 0;
    s->count = 0;
}

void 
push( stack * s, int x /*, int type*/ ) 
{ 
    if ( s->count >= STACK_SIZE ) { 
        printf( "Warning: stack overflow push x = %d\n", x );
    } else { 
        s->top = ( s->top + 1 ) % STACK_SIZE;
        s->s[ s->top ] = x;
        //s->t[ s->top ] = type;
        s->count = s->count + 1;
    }
}

int 
pop( stack * s ) 
{ 
    int x;
    
    if ( is_empty( s ) ) { printf( "Warning: empty stack pop\n" ); } 
    else { 
        x = s->s[ s->top ];
        last_elem = x;
        //last_type = s->t[ s->top ];
        s->top = ( s->top - 1 ) % STACK_SIZE;
        s->count = s->count - 1;
    }
    
    return ( x );
}

bool /*int*/ 
is_empty( stack * s ) 
{ 
    if ( s->count <= 0 ) { 
        return ( TRUE );
    } else { 
        return ( FALSE );
    }
}

/* ************************************************************************ */
/* *******************************   Main   ******************************* */
/* ************************************************************************ */

#define MAX_LEN   ( STACK_SIZE - 1 )

char brackets[ MAX_LEN + 1 ];

/* 
   Main.
 */
int 
main( void ) 
{ 
    int t;         /* number of test cases */
    //int i, j;      /* counters */
    char * b_ptr;  /* pointer for `brackets' string */
    char _top;
    
    scanf( "%d", &t );
    //printf( "%d\n", t );
loop: 
    while ( t-- ) { 
        scanf( "%s", brackets );
        //printf( "%s\n", brackets );
        b_ptr = ( char * ) brackets;
        while ( *b_ptr ) { 
            //printf( "%c", *b_ptr );
            //push( &ss, ( int ) *b_ptr );
            //printf( "%c", ( char ) pop( &ss ) );
            switch ( *b_ptr ) { 
            case '(': case '[': case '{': case '<': 
                push( &ss, ( int ) *b_ptr );
                break;
            case ')': case ']': case '}': case '>': 
                if ( is_empty( &ss ) ) { 
                    Vprintf(( "%c", *b_ptr ));
                    Vputchar(( '\n' ));
                    puts( "NO" );
                    Vputchar(( '\n' ));
                    goto loop;
                }
                _top = ( char ) pop( &ss );
                //printf( "  _top = %c\n", _top );
                //printf( "*b_ptr = %c\n", *b_ptr );
                if (    !( _top == '(' && *b_ptr == ')' ) 
                     && !( _top == '[' && *b_ptr == ']' ) 
                     && !( _top == '{' && *b_ptr == '}' ) 
                     && !( _top == '<' && *b_ptr == '>' ) ) 
                { 
                    Vprintf(( "%c", _top ));
                    Vprintf(( "%c", *b_ptr ));
                    Vputchar(( '\n' ));
                    puts( "NO" );
                    Vputchar(( '\n' ));
                    goto loop;
                }
                Vprintf(( "%c", _top ));
                Vprintf(( "%c", *b_ptr ));
                break;
            default: 
                ;
            }
            ++b_ptr;
        }
        Vputchar(( '\n' ));
        puts( is_empty( &ss ) ? "YES" : "NO" );
        Vputchar(( '\n' ));
    }
    
    return ( 0 );
}  /* main() */

/* brackets.c ends here.  */


Example

input1.txt: 
Код

8
()
(())
()()
)()(
({[<>]})
()({[<>]})()
([({})<>({})])()
(({)(}))


output1.txt: 
Код

YES
YES
YES
NO
YES
YES
YES
NO


Компиляция: 
Код

gcc brackets.c -o brackets && chmod -x brackets


Запуск: 
Код

./brackets < input1.txt


==========================================================================================
P.S. Всегда следуйте правилам форма! В частности: 
Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или флажком при ответе smile
==========================================================================================


Это сообщение отредактировал(а) V.A.KeRneL - 28.1.2007, 21:42


--------------------
«C'est un pense-creux d'ici. C'est le meilleur et le plus irascible homme du monde...» © Ф.М. Достоевский, «Бесы»
---/)/)---(\.../)---(\(\
--(':'=)---(=';'=)---(=':')
(")(")..)-(").--.(")-(..(")(")
PM MAIL IM ICQ AOL YIM MSN   Вверх
katz
Дата 29.1.2007, 20:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 8
Регистрация: 16.1.2007

Репутация: нет
Всего: нет
Спасибо парни выручили.!!!!!
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0967 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.