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

Проверка баланса скобок - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 30, средняя оценка - 4.67
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
11.03.2012, 16:09     Проверка баланса скобок #1
Как задать условие в проверке баланса скобок, что если скобки окажутся НЕ пустыми, тое сть внутри них еще что-то будет (символы или числа), допустим [(dfe)], то что бы вывело NO (ну то есть баланс нарушен). Код для проверки баланса ТОЛЬКО скобок я написал. Не знаю, как исключить другие символы.
Вот сама задача (если что-то не ясно) http://www.e-olimp.com/problems/2479 Вот мой код
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
#include<stdio.h>
int balanceBrackets(char *);
int main()
{   int p;
    char string[200]; 
    int bal; 
    scanf("%d",&p);
    for(int i=0;i<p;i++)
    {
    scanf("%s",&string);
    bal = balanceBrackets(string); 
        if (bal)
        printf("Yes\n");
        else
     printf("No\n");
    }
    return 0;
}
int balanceBrackets(char *string) 
{
    int k = 0; 
    int Open1 = 0, 
        Close1 = 0, 
        Open2 = 0, 
        Close2 = 0; 
    int index = 0; 
    bool exit = false;
    while (string[index] != '\0' && !exit) 
    {
        switch (string[index]) 
        {
        case '(':
            {
                Open1++;
                break;
            }
        case ')':
            {
                Close1++; 
                if (Close1 > Open1) exit = true; 
            }
        case '[':
            {
                Open2++; 
                break;
            }
        case ']':
            {
                Close2++;
                if (Close2 > Open2) exit = true; 
                break;
            }
        }
        index++;
    }
    if (Open1 == Close1 && Open2 ==Close2) k = 1; 
    return k; 
}
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.03.2012, 16:17     Проверка баланса скобок #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
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <stack>
#include <string>
 
bool is_correct( const std::string& );
 
int main()
{
    std::string str;
    std::cin >> str >> str;
   
    std::cout << ( is_correct(str) ? "Yes" : "No" ) << std::endl;
}
 
bool is_correct( const std::string& str)
{
    std::stack< char > stack;
   
    for (int i = 0; i < (int) str.length(); ++i)
    {
        if ( str[i] == '(' || str[i] == '{' || str[i] == '[' )
        {
            stack.push( str[i] );
        }
        else if ( str[i] == ')' || str[i] == '}' || str[i] == ']' )
        {
            if
            (
                stack.empty()
                || ( (str[i] == ')') ^ (stack.top() == '(') )
                || ( (str[i] == '}') ^ (stack.top() == '{') )
                || ( (str[i] == ']') ^ (stack.top() == '[') )  
            )
            {
                return false;
            }
           
            stack.pop();
        }
    }
   
    return stack.empty();
}
Duha666
50 / 50 / 5
Регистрация: 10.03.2012
Сообщений: 138
11.03.2012, 16:17     Проверка баланса скобок #3
Как минимум, ваша проверка неверна, тест [(]) повалит её. Нормальное решение пишется на основе стека, и его будет очень легко поправить на ваш случай:
Код
if (размер стека > 0 && ( (str[i] >= 'a' || str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z') ) )
   Всё плохо
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
11.03.2012, 16:22     Проверка баланса скобок #4
Баланс круглых скобок
[C++] Синтаксис скобок
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.03.2012, 16:22     Проверка баланса скобок #5
по вопросу
Цитата Сообщение от Джон Посмотреть сообщение
Не знаю, как исключить другие символы.
добавь ветку в свитч
C++
1
2
default:// все остальные символы
  return 0;
теперь про это
Цитата Сообщение от Джон Посмотреть сообщение
if (Open1 == Close1 && Open2 ==Close2)
если у тебя будет запись ) ( то программа тоже подсчитает что баланс есть
нужно так
переменная=0

если ( добавить 1
если ) отнять 1
если переменная меньше 0 то выход нет баланса(закрывающих больше чем открывающих)
цикл пока нет конца строки

проверить переменную 0 есть баланс
не 0 нет
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
11.03.2012, 16:28     Проверка баланса скобок #6
ValeryS, ему вроде нужно проверять и другие виды скобок (кв., треугольные и пр.)
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
11.03.2012, 16:41  [ТС]     Проверка баланса скобок #7
Пробовал реализовать все, что вы все советуете, но не засчитывает ничего нового мне((((
не получается
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
11.03.2012, 16:42     Проверка баланса скобок #8
Джон, ну так показывай, что именно (и как) ты реализовал, на каком тесте ошибается и т.д.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.03.2012, 16:43     Проверка баланса скобок #9
Цитата Сообщение от Nameless One Посмотреть сообщение
ValeryS, ему вроде нужно проверять и другие виды скобок (кв., треугольные и пр.)
ну и ????
заведи три переменных(или сколько их там)
но вот что интересно
Цитата Сообщение от Джон Посмотреть сообщение
что если скобки окажутся НЕ пустыми, тое сть внутри них еще что-то будет (символы или числа), допустим [(dfe)], то что бы вывело NO (ну то есть баланс нарушен).
{[()]}
баланс нарушен???(для фигурных и квадратных) или нет?
какие то нечеткие задания стали попадатся
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
11.03.2012, 16:48     Проверка баланса скобок #10
Цитата Сообщение от ValeryS Посмотреть сообщение
ну и ????
заведи три переменных(или сколько их там)
ValeryS, ну как, например, можно с помощью трех переменных пропарсить такое, к примеру, выражение (([)])? В конце все счетчики будут равны нулю, но тем не менее выражение не будет корректным. Или есть какой-то хитрый алгоритм?

Цитата Сообщение от Джон Посмотреть сообщение
внутри них еще что-то будет (символы или числа), допустим [(dfe)], то что бы вывело NO (ну то есть баланс нарушен)
булевый флаг, который взводится/сбрасывается на открывающей/закрывающей скобке. Когда получаем символ, не являющийся скобкой, проверяем значение флага
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.03.2012, 16:55     Проверка баланса скобок #11
Цитата Сообщение от Nameless One Посмотреть сообщение
ValeryS, ну как, например, можно с помощью трех переменных пропарсить такое, к примеру, выражение (([)])? В конце все счетчики будут равны нулю, но тем не менее выражение не будет корректным. Или есть какой-то хитрый алгоритм?
ну например так
позиция 3
переменная1(круглые скобки)равна 2
переменная2(квадратные скобки) 1
пришла закрывающая круглая скобка
проверяем переменную2 если не 0 то выходим нет баланса
если 0 то вычитаем переменную1 и продолжаем проверку
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
11.03.2012, 16:58     Проверка баланса скобок #12
Цитата Сообщение от ValeryS Посмотреть сообщение
проверяем переменную2 если не 0 то выходим нет баланса
а она не обязана быть равной нулю, в том-то и фишка. Иначе [()] тоже не пройдет
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.03.2012, 16:59     Проверка баланса скобок #13
Цитата Сообщение от Nameless One Посмотреть сообщение
булевый флаг, который взводится/сбрасывается на открывающей/закрывающей скобке. Когда получаем символ, не являющийся скобкой, проверяем значение флага
ну и твой же вопрос
(( )д)??
булева переменная сбросится на первой же закрывающей и все будет корректно(но будет ли?)
т.е только подсчет если количество равно 0 то можно символы если нет то нет баланса
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
11.03.2012, 17:03     Проверка баланса скобок #14
Цитата Сообщение от ValeryS Посмотреть сообщение
т.е только подсчет если количество равно 0 то можно символы если нет то нет баланса
нет, это не пройдет. Контрпример смотри в моем сообщении выше. А тут его объяснение:
Позиция 3
переменная1(круглые скобки)равна 1
переменная2(квадратные скобки) 1
(получает закрывающую круглую скобку)
(проверяем переменную2)
переменная2 не равна нулю — ошибка?

Но ты все еще можешь меня переубедить — просто напиши работающий код для своего алгоритма (и не стоит ограничиваться только квадратными скобками, есть еще и [], /\, {}, <>)
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.03.2012, 17:03     Проверка баланса скобок #15
Цитата Сообщение от Nameless One Посмотреть сообщение
а она не обязана быть равной нулю, в том-то и фишка.
ну тут кучу проверок нужно
по моему мы сейчас к конечным автоматам дойдем
Цитата Сообщение от Nameless One Посмотреть сообщение
[()]
если это не является балансом ( по условию не ясно)
то просто проверка несколькими функциями (каждая на свои скобки)
кстати и это не понятно (()) сбалансированы или нет
ибо
Цитата Сообщение от Джон Посмотреть сообщение
скобки окажутся НЕ пустыми, тое сть внутри них еще что-то будет
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
11.03.2012, 17:07     Проверка баланса скобок #16
Цитата Сообщение от ValeryS Посмотреть сообщение
по моему мы сейчас к конечным автоматам дойдем
автоматы, которые реализуют некоторую грамматику (в данном случае корректные сбалансированные скобочные конструкции), пишут не через счетчики, потому, как ты уже сам сказал, нужна куча проверок (мне, к примеру, совсем не очевидно, можно ли эти проверки написать).
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.03.2012, 17:11     Проверка баланса скобок #17
Цитата Сообщение от Nameless One Посмотреть сообщение
Но ты все еще можешь меня переубедить, просто напиши работающий код для своего алгоритма
Да лень мне
можно ввести еще одну переменную-перечисление где записавшем последнюю открывающую скобку
и если закрывающая не равна то ошибка

и вообще для таких вещей стек придуман
если такие сложные условия то он то будет в самый раз
открывающая запихиваем
закрывающая выпихиваем
закрывающая парная открывающей идем дальше
нет выходим с ошибкой
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.03.2012, 17:12     Проверка баланса скобок
Еще ссылки по теме:

Проверка правильности расстановки скобок в строке (рекурсия) C++
C++ Проверка баланса скобок арифметического выражения, введенного с клавиатуры
Составить программу проверки баланса скобок арифметического выражения, введенного с клавиатуры C++

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

Или воспользуйтесь поиском по форуму:
Duha666
50 / 50 / 5
Регистрация: 10.03.2012
Сообщений: 138
11.03.2012, 17:12     Проверка баланса скобок #18
Вариант под три типа скобок: (){}[]
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
#include <stdio.h>
 
using namespace std;
 
char s[500], str[500];
int r;
bool bad;
 
int main()
{
    gets(str);
    for (int i = 0; str[i] != 0; i++)
    {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{')
            s[r++] = str[i];
        else
            if (str[i] == ')' || str[i] == ']' || str[i] == '}')
            {
                if (r == 0 || (str[i] == ')' && s[r - 1] != '(') || (str[i] == ']' && s[r - 1] != '[') || (str[i] == ']' && s[r - 1] != '['))
                {
                    bad = true;
                    break;
                }
                r--;
            }
            else
                if (r > 0)
                {
                    bad = true;
                    break;
                }
    }
    if (r > 0)
        bad = true;
    printf("%d", bad);
 
}
Yandex
Объявления
11.03.2012, 17:12     Проверка баланса скобок
Ответ Создать тему
Опции темы

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