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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.75
влад-мармелад
0 / 0 / 0
Регистрация: 12.04.2009
Сообщений: 22
#1

Баланс скобок - C++

24.04.2009, 19:44. Просмотров 1951. Ответов 14
Метки нет (Все метки)

Добавьте плиз условие чтоб )(-говорило что не баланс..я прост незнаю
Код
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAXVAL 100

struct stack {
int sp;
int val[MAXVAL]; /* массив под скобки */
} mystack;

/* push: добавить элемент в стек */
void push(int c)
{
if(mystack.sp < MAXVAL)
mystack.val[mystack.sp++] = c;
else
printf("error: stack is fulled!\n");
}

/* pop: взять элемент из стека */
int pop(void)
{
if(mystack.sp > 0)
return mystack.val[--mystack.sp];
else
return EOF;
}

main()
{
FILE *fp;
int c,
marker = '!', /* маркер */
br1, br2, isbr; /* счетчики скобок */

mystack.sp = 0;
isbr = br1 = br2 = 0;
if( (fp = fopen("in.txt", "r")) == NULL) {
printf("error: can't open in.txt");
getch();
return 0;
}
while((c = getc(fp)) != EOF && c != marker) /* добавление скобок в стек */
if(c == '(' || c == ')') {
push(c);
isbr = 1;
}
while((c = pop()) != EOF) { /* извлечение скобок из стека */
if(c == '(')
br1++;
else if(c == ')')
br2++;
}
if(br1 != br2 && isbr != 0)
printf("\n\tUnbalanced brackets.");
else if(isbr == 0)
printf("\n\tNo brackets.");
else
printf("\n\tBalance.");
fclose(fp);
getch();
return 0;
}
эта программа проверяет баланс скобок скажите как можно сделать чтобы скобки )(-говорило что не баланс???не используя библиотеку стринг и списки..)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Evg
Эксперт CАвтор FAQ
17317 / 5565 / 347
Регистрация: 30.03.2009
Сообщений: 15,129
Записей в блоге: 26
24.04.2009, 20:03     Баланс скобок #2
У тебя подход к задаче неправильный. Ты прочитал все левые и правые скобки и напихал их в стек, а потом их все оттуда достал. Т.е непонятно вообще зачем тут стек (мог бы и в обычный буффер поместить)

Правильный подход такой: в первом же цикле, где ты считываешь из файла:
1. При чтении левой скобки суёшь её в стек
2. При чтении правой скобки:
- если стек пуст, значит ошибка - лишняя (несбаллансированная) правая скобка
- достаёшь значение из стека (что там можно не смотреть, потому что суёшь ты только левые скобки).
3. По окнчании цикла проверяешь стек, если стек не пустой, значит присуствуют лишние (несбаллансированные) левые скобки

Это в том случае, если тебе поставлена задача обязательно стек использовать. Если стек не нужно, то просто используй счётчик. Для левой скобки увеличивай, для правой уменьшай. Если счётчик стал отрицательным - лишняя правая скобка. Если по окончании счётчик не равен нулю - значит есть лишние левые скобки
влад-мармелад
0 / 0 / 0
Регистрация: 12.04.2009
Сообщений: 22
24.04.2009, 20:30  [ТС]     Баланс скобок #3
С обычым буфером все понятно прост как сделать именно для )(-что это не баланс если без стека?
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 20:36     Баланс скобок #4
Цитата Сообщение от влад-мармелад Посмотреть сообщение
С обычым буфером все понятно прост как сделать именно для )(-что это не баланс если без стека?
->
Цитата Сообщение от влад-мармелад Посмотреть сообщение
Если стек не нужно, то просто используй счётчик. Для левой скобки увеличивай, для правой уменьшай. Если счётчик стал отрицательным - лишняя правая скобка. Если по окончании счётчик не равен нулю - значит есть лишние левые скобки
влад-мармелад
0 / 0 / 0
Регистрация: 12.04.2009
Сообщений: 22
24.04.2009, 20:37  [ТС]     Баланс скобок #5
так и говорю...)(-это при таком подходе будет говорить что баланс ведь есть и открывающая и закрывающая скобка..
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
24.04.2009, 20:40     Баланс скобок #6
внимательно читаем ,что Evg написал
влад-мармелад
0 / 0 / 0
Регистрация: 12.04.2009
Сообщений: 22
24.04.2009, 23:41  [ТС]     Баланс скобок #7
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
while((c = getc(fp)) != EOF && c != marker)    /* добавление скобок в стек */
       if(c == '(' ){
          push(c);
          isbr1 = 1;}
 
        else if(c == ')')
        { push(c);
          isbr2=1; 
         } 
       }
while((c = pop()) != EOF) { /* извлечение скобок из стека */
if(c == '(')
br1++;
else if(c == ')')
br2++;
}
if(br1!=br2&&isbr1==br2)
printf("\n\tbracket found.");
else if(isbr2 == br1)
printf("\n\tNo brackets.");
else
printf("\n\tBalance.");
fclose(fp);
getch();
return 0;
}
мож вот так?
Evg
Эксперт CАвтор FAQ
17317 / 5565 / 347
Регистрация: 30.03.2009
Сообщений: 15,129
Записей в блоге: 26
24.04.2009, 23:42     Баланс скобок #8
Неправильно
У тебя в первом цикле суются в стек только левые скобки, затем у тебя идёт второй цикл, гле суются правые скобки (но цикл этот ни разу не исполнится, т.к. мы уже дошли до конца файла)

То, что я тебе писал выше, нужно делать в одном цикле
влад-мармелад
0 / 0 / 0
Регистрация: 12.04.2009
Сообщений: 22
24.04.2009, 23:47  [ТС]     Баланс скобок #9
я тут опять немного переправил посмотри выше?не так ли?
Evg
Эксперт CАвтор FAQ
17317 / 5565 / 347
Регистрация: 30.03.2009
Сообщений: 15,129
Записей в блоге: 26
24.04.2009, 23:51     Баланс скобок #10
Ты написал второй вариант - во втором if'е, где else if(c == ')') надо делать pop
Т.е. при достижении левый скобки засовываем в стек (push), а при достижении правой скобки высовываем из стека (pop) то, что там лежит (зотя что там лежит, нам не важно)

Давай просто попробуем смоделировать стек звёздочками
У тебя выражение "((())())"
Начало: стек пустой
1-й символ = '(' - push, стек стал такой: *
2-й символ = '(' - push, стек стал такой: **
3-й символ = '(' - push, стек стал такой: ***
4-й символ = ')' - pop, стек стал такой: **
5-й символ = ')' - pop, стек стал такой: *
6-й символ = '(' - push, стек стал такой: **
7-й символ = ')' - pop, стек стал такой: *
8-й символ = ')' - pop, стек стал пустой
При этом неважно, что пихать в стек, я пихал туда звёздочки. Нам важно лишь состояние стека (грубо говоря, количество элементов)

Теперь неправильное выражение с избытком правых скобок: (()))
Начало: стек пустой
1-й символ = '(' - push, стек стал такой: *
2-й символ = '(' - push, стек стал такой: **
3-й символ = ')' - pop, стек стал такой: *
4-й символ = ')' - pop, стек стал пустой
5-й символ = ')' - pop, но стек уже пустой, а потому pop сделать не можем - ошибка (избыток правх скобок)

Теперь неправильное выражение с избытком левых скобок: ((())
Начало: стек пустой
1-й символ = '(' - push, стек стал такой: *
2-й символ = '(' - push, стек стал такой: **
3-й символ = '(' - push, стек стал такой: ***
4-й символ = ')' - pop, стек стал такой: **
5-й символ = ')' - pop, стек стал такой: *
Сиволы кончились, но стек у нас не пустой -ошибка (избыток левых скобок)
влад-мармелад
0 / 0 / 0
Регистрация: 12.04.2009
Сообщений: 22
24.04.2009, 23:57  [ТС]     Баланс скобок #11
хм...а что если вставить в мою... изначальную прогу самую первую в цикл
if(br2>br1) printf("\nError");?может так легче будет?)
Evg
Эксперт CАвтор FAQ
17317 / 5565 / 347
Регистрация: 30.03.2009
Сообщений: 15,129
Записей в блоге: 26
25.04.2009, 00:02     Баланс скобок #12
Цитата Сообщение от влад-мармелад Посмотреть сообщение
хм...а что если вставить в мою... изначальную прогу самую первую в цикл
if(br2>br1) printf("\nError");?может так легче будет?)
В принципе, да. Но учти, что скобки из стека ты достаёшь в обратном порядке. Т.е. твоё использование стека не по назначению только усложняют порядок. Но переделать можно. Т.е. как-то нужно пространственное воображение иметь, чтобы видя скобки в обратном порядке их проверять. Тогда можешь ввобще стек не использовать. Читаешь в цикле из файла (т.е. while((c = getc(fp)) != EOF ...) но при этом дулаешь то, что у тебя записано во втором цикле (подсчёт br1 и br2)
влад-мармелад
0 / 0 / 0
Регистрация: 12.04.2009
Сообщений: 22
25.04.2009, 00:22  [ТС]     Баланс скобок #13
Читаешь в цикле из файла (т.е. while((c = getc(fp)) != EOF ...) но при этом дулаешь то, что у тебя записано во втором цикле (подсчёт br1 и br2)

а можно это по подробнее объяснить?)кстати спасибо что на меня время тратишь..)
Evg
Эксперт CАвтор FAQ
17317 / 5565 / 347
Регистрация: 30.03.2009
Сообщений: 15,129
Записей в блоге: 26
25.04.2009, 00:29     Баланс скобок #14
Цитата Сообщение от влад-мармелад Посмотреть сообщение
а можно это по подробнее объяснить?
Сейчас у тебя сделано так. В первом цикле ты читаешь все байты и если этот байт - скобка, то ты его push в стек. Во втором цикле ты всё достаёшь из стека и при этом ведёшь подсчёт количества левых и правых скобок.

Я предлагаю сделать так. Делаешь только один цикл, в котором читаешь все байты и если этот байт - левая скобка, то делаешь подсчёт левых скобок, если правая - подсчёт правых (т.е. то, что ты делаешь во втором цикле). При этом стек тебе не нужен вообще

Цитата Сообщение от влад-мармелад Посмотреть сообщение
кстати спасибо что на меня время тратишь..)
Я не сторонник того, чтобы выкладывать на блюдечке готовое решение. У тебя вроде бы как есть желание разобраться и сделать самому, так отчего же не помочь
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.04.2009, 13:32     Баланс скобок
Еще ссылки по теме:

Ввести строку символов и найти баланс открывающихся и закрывающихся скобок C++
Баланс скобок C++
C++ Проверить баланс скобок в тексте программы
Проверять строку на баланс скобок C++
C++ Проверить баланс круглых скобок, используя очередь

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

Или воспользуйтесь поиском по форуму:
Gravity
557 / 551 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
25.04.2009, 13:32     Баланс скобок #15
Подправил.
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
66
67
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAXVAL 100
 
struct stack {
    int sp;
    int val[MAXVAL];   /* массив под скобки */
} mystack;
 
/* push: добавить элемент в стек */
void push(int c)
{
    if(mystack.sp < MAXVAL)
       mystack.val[mystack.sp++] = c;
    else
       printf("error: stack is fulled!\n");
}
 
/* pop: взять элемент из стека */
int pop(void)
{
    if(mystack.sp > 0)
       return mystack.val[--mystack.sp];
    else
      return EOF;
}
 
main()
{
    FILE *fp;
    int c, 
        marker = '!',    /* маркер */
        isbr;  /* флаг наличия скобок */
    
    mystack.sp = isbr = 0;
    if( (fp = fopen("in.txt", "r")) == NULL) {
       printf("error: can't open in.txt");
       getch();
       return 0;
    }
    while((c = getc(fp)) != EOF && c != marker) {
       if(c == '(') {
          push(c);
          isbr = 1;
        }
        else if(c == ')') {
           if(mystack.sp < 1) {
              printf("\n\tUnbalanced brackets.\n");
              getch();
              fclose(fp);
              return 0;
           } else
              pop();
       }
    }     
    if(mystack.sp > 0 && isbr)
       printf("\n\tUnbalanced brackets.\n");
    else if(!isbr)
       printf("\n\tNo brackets.\n");
    else
       printf("\n\tBalance.\n");
       
    fclose(fp);
    getch();
    return 0;
}
Yandex
Объявления
25.04.2009, 13:32     Баланс скобок
Ответ Создать тему
Опции темы

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