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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.88
crazygor1
6 / 6 / 1
Регистрация: 06.02.2010
Сообщений: 131
#1

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

27.10.2010, 17:37. Просмотров 2239. Ответов 15
Метки нет (Все метки)

Доброго время суток! Помогите реализовать задачу:
Данн массив (char). В нём записанн какой-нибудь пример со скобками, скобки только такие - ().
Проверить правельно ли стот скобки.
Заранее спасибо!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.10.2010, 17:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Проверка скобочной записи (C++):

Реализация скобочной записи дерева - C++
#include <iostream> using namespace std; struct node { int info; node *left, *right; }; node *vvod(void); void...

Стековая реализация проверки правильности скобочной последовательности - C++
Надо проверить, верна ли скобочная последовательность. Решение с помощью стека. Программа ломается на самом простом тесте(лол) : (). Но я...

Проверка на существование конкретной записи в файле - C++
Добрый день! Хочу проверить есть ли в файле уже введёный пользователем ID. Если такой ID уже есть, то вывести сообщение об этом и...

Проверка на повтор при записи в файл - C++
Уважаемые, нужна помощь!!Суть вот в чём, в файл записываются данные(символы, цифры и т.п) и надо сделать так, что бы не было повторов, ...

Проверка чисел на простоту и проверку на наличие общих цифр в записи - C++
Помогите написать программу: Для каждого (n) из некоторого количества натуральных чисел указать простое число К, ближайшее к числу n и...

Проверка текста на правильность записи числа от 1 до 1999 римскими цифрами - C++
Привет! Нужна ваша помощь. Поставлена следующая задача: Если заданный текст является правильной записью римскими цифрами целого числа от...

15
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
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;
}
2
crazygor1
6 / 6 / 1
Регистрация: 06.02.2010
Сообщений: 131
27.10.2010, 17:54  [ТС] #3
Можно коменты плз
#include <stdio.h> подскжите плз что это за библиотека?)
Я просто пока учусь писать проги в коммандной строке и некоторое из этого мне не понятно
0
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
27.10.2010, 17:59 #4
Проверка правильности скобочной конструкции заключается в подсчете открывающих и закрывающих скобок. Если встречается открывающая скобка, то счетчик увеличивается на единицу, если закрывающая - то счетчик уменьшается на единицу. Если на любом шаге цикла счетчик примет отрицательное значение (т.е. закрывающая скобка встретилась раньше соответствующей открывающей), то скобочная конструкция - однозначно неправильная, и дальше проверять ее нет смысла. Если после проверки всей строки счетчик равен нулю, то конструкция правильная, в противном случае - нет
1
dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 284
27.10.2010, 18:20 #5
проверку скобок можно красиво сделать через стек.
0
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
27.10.2010, 18:24 #6
Цитата Сообщение от dxdy Посмотреть сообщение
проверку скобок можно красиво сделать через стек.
Если встретился символ '(', то помещаем его в стек, если ')' - вынимаем символ из стека. Так что ли?
0
dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 284
28.10.2010, 14:05 #7
Nameless One ага, удобно, если в выражении присутствуют разные виды скобок. Например:
() {} <>
0
st_dent
64 / 64 / 3
Регистрация: 05.07.2010
Сообщений: 219
28.10.2010, 14:08 #8
Цитата Сообщение от dxdy Посмотреть сообщение
проверку скобок можно красиво сделать через стек.
Можно примерчик?
0
dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 284
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;
}
2
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
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;
}
1
dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 284
28.10.2010, 15:00 #11
Nameless One при только открывающихся скобках ваша программа сломается
const char* expr = "(((";
1
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
28.10.2010, 15:11 #12
Точно. Тогда нужно заменить строку 56 на
C++
1
return stk.empty();
0
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
0
DU
1484 / 1130 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
15.09.2012, 16:21 #14
с разными скобками не все так просто.
вот строка:
"({)}" - вроде как число открывающих и закрывающих скобок правильное, но в большинстве кейсов такая строка все таки не является корректной с точки зрения расставления скобок.
0
valeriikozlov
Эксперт С++
4675 / 2501 / 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";
1
15.09.2012, 17:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.09.2012, 17:12
Привет! Вот еще темы с ответами:

Проверка записи на соответствие условию: правильная скобочная запись из круглых и квадратных скобок - C++
Здравствуйте! Задача: проверка записи на соответствие условию: правильная скобочная запись из круглых и квадратных скобок, внутри...

Visual C++ проверка ввода на число, проверка на кирилицу - C++
Суть ввести с клавиатуры нечто, и повторять ввод до тех пор пока введенное число не будет числом. Этот код проверяет на буквы и знаки,...

Написать функции для чтения/записи отдельных бит для любой записи из данного набора - C++
Начиная с адреса А в памяти МК находятся N записей длиной k бит каждая. Записи выровнены по границе слова. Написать функции для...

Машина Тьюринга. Проверка скобочной последовательности - Java SE
Добрый день. Возникла такая задача - реализовать машину Тьюринга для проверки правильности скобочной последовательности. Описание мат....


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

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

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