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

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

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

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

24.04.2009, 19:44. Просмотров 2028. Ответов 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;
}
эта программа проверяет баланс скобок скажите как можно сделать чтобы скобки )(-говорило что не баланс???не используя библиотеку стринг и списки..)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2009, 19:44
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Баланс скобок (C++):

Баланс скобок - C++
Люди может укажите мне на ошибку в программе по которой не находит баланс..? #include&lt;iostream.h&gt; #include&lt;string.h&gt; ...

Баланс скобок - C++
Доброе утро, мне было задано написать программу о том, соответствует ли каждой открывающей скобке, каждая закрывающая, среди символов...

Баланс скобок - C++
Помогите пожалуйста!!! Собственно задание: Текст в файле содержит многократно вложенные круглые скобки. Если баланс скобок соблюден,...

Баланс скобок - C++
проверить правильность расстановки скобок, используя контейнерные типы(стек)

Баланс круглых скобок - C++
Проверить, соблюдается ли в тексте баланс круглых скобок. Для каждой открывающей скобки ‘(‘ должна быть найдена соответствующая закрывающая...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Evg
Эксперт CАвтор FAQ
17624 / 5848 / 375
Регистрация: 30.03.2009
Сообщений: 16,124
Записей в блоге: 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
17624 / 5848 / 375
Регистрация: 30.03.2009
Сообщений: 16,124
Записей в блоге: 26
24.04.2009, 23:42 #8
Неправильно
У тебя в первом цикле суются в стек только левые скобки, затем у тебя идёт второй цикл, гле суются правые скобки (но цикл этот ни разу не исполнится, т.к. мы уже дошли до конца файла)

То, что я тебе писал выше, нужно делать в одном цикле
влад-мармелад
0 / 0 / 0
Регистрация: 12.04.2009
Сообщений: 22
24.04.2009, 23:47  [ТС] #9
я тут опять немного переправил посмотри выше?не так ли?
Evg
Эксперт CАвтор FAQ
17624 / 5848 / 375
Регистрация: 30.03.2009
Сообщений: 16,124
Записей в блоге: 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
17624 / 5848 / 375
Регистрация: 30.03.2009
Сообщений: 16,124
Записей в блоге: 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
17624 / 5848 / 375
Регистрация: 30.03.2009
Сообщений: 16,124
Записей в блоге: 26
25.04.2009, 00:29 #14
Цитата Сообщение от влад-мармелад Посмотреть сообщение
а можно это по подробнее объяснить?
Сейчас у тебя сделано так. В первом цикле ты читаешь все байты и если этот байт - скобка, то ты его push в стек. Во втором цикле ты всё достаёшь из стека и при этом ведёшь подсчёт количества левых и правых скобок.

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

Цитата Сообщение от влад-мармелад Посмотреть сообщение
кстати спасибо что на меня время тратишь..)
Я не сторонник того, чтобы выкладывать на блюдечке готовое решение. У тебя вроде бы как есть желание разобраться и сделать самому, так отчего же не помочь
Gravity
562 / 556 / 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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.04.2009, 13:32
Привет! Вот еще темы с ответами:

Баланс скобок в файле - C++
#include&lt;fstream.h&gt; #include&lt;iostream.h&gt; #include&lt;string.h&gt; #include&lt;conio.h&gt; #include&lt;stdio.h&gt; int...

Проверять строку на баланс скобок - C++
Драствуйте. Условие такое - написать програмку которая будет проверять строку на баланс скобок (закрытые, открытые) и чтобы текст читало с...

Проверить баланс скобок в текстовом файле - C++
1. из файла f1 выводится текст (текст со скобками) 2. проверяется соответствие скобок 3. если не соответствуют, то в фаил f2 вводиться...

Проверить баланс скобок в тексте программы - C++
Задача: Создать файл в котором есть программа бейсик. Проверить на соответствие открытые и закрытые скобки. Как отрыть файл и считать с...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
25.04.2009, 13:32
Ответ Создать тему
Опции темы

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