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

Проверка скобочной записи - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.88
crazygor1
 Аватар для crazygor1
6 / 6 / 1
Регистрация: 06.02.2010
Сообщений: 131
27.10.2010, 17:37     Проверка скобочной записи #1
Доброго время суток! Помогите реализовать задачу:
Данн массив (char). В нём записанн какой-нибудь пример со скобками, скобки только такие - ().
Проверить правельно ли стот скобки.
Заранее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.10.2010, 17:37     Проверка скобочной записи
Посмотрите здесь:

Есть в записи числа m цифры, которые совпадают с цифрами в записи числа n C++
C++ Проверка чисел на простоту и проверку на наличие общих цифр в записи
Проверка записи на соответствие условию: правильная скобочная запись из круглых и квадратных скобок C++
Написать функции для чтения/записи отдельных бит для любой записи из данного набора C++
Проверка на повтор при записи в файл C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
27.10.2010, 17:54     Проверка скобочной записи #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
27
28
29
30
#include <stdio.h>
 
int func(const char* str, int cnt)
{
    if(cnt < 0)
        return 0;
    if(*str)
    {
        switch(*str)
        {
        case '(':
            return func(++str, ++cnt);
        case ')':
            return func(++str, --cnt);
        default:
            return func(++str, cnt);
        }
    }
    return (cnt == 0 ? 1 : 0);
}
 
int main()
{
    const char* foo = "((d )(sf()kl( ))()";
    if(func(foo, 0))
        puts("Correct!");
    else
        puts("Incorrect!");
    return 0;
}
Вот без рекурсии:
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
#include <stdio.h>
 
int func(const char* str)
{
    int cnt;
    for(cnt = 0; (cnt >= 0) && (*str); ++str)
        switch(*str)
        {
        case '(':
            ++cnt;
            break;
        case ')':
            --cnt;
        }
        
    return (cnt == 0 ? 1 : 0);
}           
 
int main()
{
    const char* foo = ")((d )(sf()kl( ))())";
    if(func(foo))
        puts("Correct!");
    else
        puts("Incorrect!");
    return 0;
}
crazygor1
 Аватар для crazygor1
6 / 6 / 1
Регистрация: 06.02.2010
Сообщений: 131
27.10.2010, 17:54  [ТС]     Проверка скобочной записи #3
Можно коменты плз
#include <stdio.h> подскжите плз что это за библиотека?)
Я просто пока учусь писать проги в коммандной строке и некоторое из этого мне не понятно
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
27.10.2010, 17:59     Проверка скобочной записи #4
Проверка правильности скобочной конструкции заключается в подсчете открывающих и закрывающих скобок. Если встречается открывающая скобка, то счетчик увеличивается на единицу, если закрывающая - то счетчик уменьшается на единицу. Если на любом шаге цикла счетчик примет отрицательное значение (т.е. закрывающая скобка встретилась раньше соответствующей открывающей), то скобочная конструкция - однозначно неправильная, и дальше проверять ее нет смысла. Если после проверки всей строки счетчик равен нулю, то конструкция правильная, в противном случае - нет
dxdy
 Аватар для dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
27.10.2010, 18:20     Проверка скобочной записи #5
проверку скобок можно красиво сделать через стек.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
27.10.2010, 18:24     Проверка скобочной записи #6
Цитата Сообщение от dxdy Посмотреть сообщение
проверку скобок можно красиво сделать через стек.
Если встретился символ '(', то помещаем его в стек, если ')' - вынимаем символ из стека. Так что ли?
dxdy
 Аватар для dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
28.10.2010, 14:05     Проверка скобочной записи #7
Nameless One ага, удобно, если в выражении присутствуют разные виды скобок. Например:
() {} <>
st_dent
64 / 64 / 3
Регистрация: 05.07.2010
Сообщений: 219
28.10.2010, 14:08     Проверка скобочной записи #8
Цитата Сообщение от dxdy Посмотреть сообщение
проверку скобок можно красиво сделать через стек.
Можно примерчик?
dxdy
 Аватар для dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
28.10.2010, 14:25     Проверка скобочной записи #9
Код
#include <iostream>
#include <stack>

//--------------------------
bool testStack(char *str){
	std::stack<int> stk;

	while(*str){
		if( *str == '(' ){
			stk.push(0);
		}else{
			if( *str == ')' ){
				if( stk.empty() )
					return false;
				else
					stk.pop();
			}
		}
		++str;
	}
	return stk.empty();
}

int main(){
	std::cout << testStack("()()(())") << std::endl;
	return 0;
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
28.10.2010, 14:50     Проверка скобочной записи #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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <stack>
 
char lb ( char rb )
{
    switch ( rb )
    {
    case ')':
        return '(';
 
    case '}':
        return '{';
 
    case ']':
        return '[';
 
    case '>':
        return '<';
 
    default:
        return 0;
    }
}
 
bool checkb ( const char* expr )
{
    std::stack<char> stk;
 
    while ( *expr )
    {
        switch ( *expr )
        {
        case '(':
        case '{':
        case '[':
        case '<':
            stk.push ( *expr++ );
            break;
 
        case ')':
        case '}':
        case ']':
        case '>':
 
            if ( stk.empty() || ( stk.top() != lb ( *expr++ ) ) )
                return false;
 
            stk.pop();
            break;
 
        default:
            expr++;
        }
    }
 
    return true;
}
 
int main()
{
    const char* expr = "< ( foo [ ] { () } ) >";
    std::cout << '\''  << expr << "\' is a correct bracket construction? -- ";
    std::cout << std::boolalpha << checkb ( expr ) << std::endl;
    return 0;
}
dxdy
 Аватар для dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
28.10.2010, 15:00     Проверка скобочной записи #11
Nameless One при только открывающихся скобках ваша программа сломается
const char* expr = "(((";
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
28.10.2010, 15:11     Проверка скобочной записи #12
Точно. Тогда нужно заменить строку 56 на
C++
1
return stk.empty();
konstantin2014
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 5
15.09.2012, 15:27     Проверка скобочной записи #13
привет,можете пожалуйста посмотреть код программы и указать на ошибки,не компилируется,мне кажется,что у меня ошибка в типе данных.пользователь вводит скобочную последовательность из ( и ) скобок,если правильная,то программа выводит 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
#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
int main()
{
    string strscob;
    cin >> strscob;
    char openscob = '(';
    char closescob = ')';
    int i,j,f;
    i = 0;
    f = 0;
    for ( int j = 0; j < strscob.length(), j++)
    {
        if (strscob[j] = openscob) i++;
        else i--;
           if (i < 0)
        {
            f = 1;
            break;
        }
 
    }
    if (f||i)
    cout << "NO"
    else
    cout << "YES"
    return 0;
 
}
компилировал и пытался запустить в CodeBlocks
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
15.09.2012, 16:21     Проверка скобочной записи #14
с разными скобками не все так просто.
вот строка:
"({)}" - вроде как число открывающих и закрывающих скобок правильное, но в большинстве кейсов такая строка все таки не является корректной с точки зрения расставления скобок.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.09.2012, 17:12     Проверка скобочной записи #15
Цитата Сообщение от konstantin2014 Посмотреть сообщение
C++
1
for ( int j = 0; j < strscob.length(), j++)
заменить на:
C++
1
   for (  j = 0; j < strscob.length(); j++)

Цитата Сообщение от konstantin2014 Посмотреть сообщение
C++
1
2
3
4
if (f||i)
 cout << "NO"
 else
 cout << "YES"
заменить на:
C++
1
2
3
4
   if (f||i)
    cout << "NO";
    else
    cout << "YES";
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.09.2012, 12:04     Проверка скобочной записи
Еще ссылки по теме:

C++ Проверка текста на правильность записи числа от 1 до 1999 римскими цифрами
C++ Реализация скобочной записи дерева
C++ Проверить, есть ли в записи числа m цифры, совпадающие с цифрами в записи числа n

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

Или воспользуйтесь поиском по форуму:
konstantin2014
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 5
16.09.2012, 12:04     Проверка скобочной записи #16
спасибо

Добавлено через 18 часов 8 минут
здравствуйте,можете подсказать пожалуйста алгоритм проверки правильности скобочной последовательности с использованием vector?
Yandex
Объявления
16.09.2012, 12:04     Проверка скобочной записи
Ответ Создать тему
Опции темы

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