IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> э-э-э .. просто скобки., разбор выражений со скобками
сообщение
Сообщение #1


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Хочу написать прогу, которая разбирает выражения со скобками, например, если
(6[0)888]{99} значит, прога выводит
(6[0)
[0)888]
{99}
возникла проблема с алгоритмом. Предположим, выражение представлено ввиде строки. Тогда я ищу первую открывающуюся скобку с начала строки, а затем соответствующую ей закрывающуюся скобку с конца строки и вывожу все ,что между ними, затем ищу вторую открывающуюся скобку ит.д. НО если я введу такое выражение [6(7]8[9]), то если действовать по этому алгоритму выведется совсем не то, что надо, а именно,
[6(7]8[9]
(7]8[9])
[9]
а ведь должно быть
[6(7]
(7]8[9])
[9]
Подскажите, как быть в такой ситуации?

Сообщение отредактировано: Тёмный Эльф -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Вообще не очень понятно, чего именно ты хочешь, но если я угадал, то тебе надо идти не с конца - влево, а от той скобки, для которой ищешь пару - вправо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Цитата
значит, прога выводит


А то что баланс скобок не соблюден это нормально ?


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Не-е баланс скобок обязателен конечно. Это я сглючила..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


В таком случае посмотри обратную польскую запись.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Пожалуйста помогите разобраться с прогой, всё не могу довести её до ума.
Сейчас она корректно вроде разбирается с выражением, где каждый вид скобок ('(', '[', '{', '<') встречается лишь однажды. Например, если вводим (ma)[pa]<da>, то выводится
(ma)
[pa]
<da>
а если вводим (ma[pa]da)<ya> , то программа выдаст
(ma[pa]da)
[pa]
<ya>
То есть найдя с начала строки скобку, ищем такую же с конца. Потом запоминаем место ,где нашли первую скобку, идем в рекурсию, и так до конца строки.
Но например если вводим (ma)(ma)[pa], то уже возникают проблемы, надо
(ma)
(ma)
[pa], а прога естественно выводит
(ma)(ma)
[pa], потому что ищет такую же скобку с конца! Нет, можно было бы конечно, искатбь закрывающуюся скобку с начала строки, но тогда еси мы введем такое выражение (ma)(ma){pa{pa}da} получится
(ma)
(ma)
{pa{pa}
{pa}
неправильно же! надо
(ma)
(ma)
{pa{pa}da}
{pa}
В-общем, я совсем запуталась..есть ли у кого-нибудь идеи?


#include <stdio.h>
#include <string.h>
#include <conio.h>
int dlina_stroki;
char stroka[80];

void f1 (char s1[80],int i)
{
int n,k; char ch;
while (s1[i]!= '(' && s1[i] != '[' && s1[i] != '{' && s1[i] != '<') {i=i+1;}

switch (s1[i])
{
case '(': {ch=')'; break;}
case '[': {ch=']'; break;}
case '<': {ch='>'; break;}
case '{': {ch='}'; break;}
}
n=i;
i=dlina_stroki;
while (s1[i] != ch) {i=i-1;}
k=i;
for (i=n; i<=k; i++)
printf("%c",s1[i]);
i=n+1;
if (i<dlina_stroki) { printf("\n%c",' '); f1(s1,i);}
}

void main(void)
{ int i;
clrscr();
printf("Enter the string please\n");
gets(stroka);
dlina_stroki=strlen(stroka);
i=0;
f1(stroka,i);
}

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(Тёмный Эльф @ 26.04.2007 22:16) *

То есть найдя с начала строки скобку, ищем такую же с конца

А надо не с конца искать, а продолжать от скобки вперед. т.е. нашел скобку "(", идешь вперед и ищещь соответствующую закрывающую (Заводишь счетчик, к нему +1, если попадалась открывающая, -1 -закрывающая - на нужной закрывающей счетчик будет = 0).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Цитата
А надо не с конца искать, а продолжать от скобки вперед. т.е. нашел скобку "(", идешь вперед и ищещь соответствующую закрывающую


но если мы будем продолжать от скобки вперед ,то например, такое выражение
(ma(da)ma) прога выведет как
(ma(da)
(da)ma), а надо:
(ma(da)ma)
(da)
или все дело в счетчике? я не совсем поняла его роль , можно пожалуйста поподробнее?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






(ma(da)ma)
первая открывающаяся скобка - счетчик присвоим 1...
- пропускаем
вторая открывающаяся - увеличим счетчик ( = 2 )
da - пропустили
одна скобка закрылась, уменьшить счетчик ( = 1 )

... продолжать до тех пор, пока счетчик не будет равен 0... А случится это на второй закрывающей скобке... Это и будет скобка, закрывающая первую открытую...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


ну наконец то дошло..спасибо! буду реализовать.. =)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Хм.. я что-то делаю не так? Не понимаю ,где ошибка. Вроде все цивильно. вроде.

#include <stdio.h>
#include <string.h>
#include <conio.h>
int dlina_stroki;
char stroka[80];

void f1 (char s1[80],int i)
{
int n,k,kok; char ch,ch_1;
while (s1[i]!= '(' && s1[i] != '[' && s1[i] != '{' && s1[i] != '<') {i=i+1;}

switch (s1[i])
{
case '(': {ch=')'; ch_1='(';break;}
case '[': {ch=']'; ch_1='[';break;}
case '<': {ch='>'; ch_1='<';break;}
case '{': {ch='}'; ch_1='{';break;}
}
n=i;
i=n+1;
kok=1;
do
{if (s1[i]=ch_1) kok=kok+1;
if (s1[i]=ch) kok=kok-1;
i=i+1;
} while (kok != 0 & i<=dlina_stroki);
k=i;

for (i=n; i<=k; i++)
printf("%c",s1[i]);
i=n+1;
if (i<dlina_stroki) { printf("\n%c",' '); f1(s1,i);}
}

void main(void)
{ int i;
clrscr();
printf("Enter the string please\n");
gets(stroka);
dlina_stroki=strlen(stroka);
i=0;
f1(stroka,i);
}


Ошибки как таковой нет ,но выдаёт программа полный бред. мой бред.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Цитата
Вроде все цивильно
С точки зрения синтаксиса (в логике - не разбирался, поздно уже smile.gif ) - не совсем...

if (s1[i]=ch_1) kok=kok+1; // <--- Это что, сравнение?
if (s1[i]=ch) kok=kok-1; // и это тоже?
Только в С/С++ сравнение - это двойной знак равенства...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Цитата
С точки зрения синтаксиса (в логике - не разбирался, поздно уже smile.gif ) - не совсем...


да равенство неверно было записано.. но там не из-за этого бред выходит.. в логике дело.

Сообщение отредактировано: Тёмный Эльф -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Все равно не понимаю, где ошибка!
Вот в мэйн я присваиваю i=0, после вызываю процедуру
f1(stroka,i);
В процедуре происходит вот что:
сначала мы пробегаем по всей строке в поисках открывающейся скобки

while (s1[i]!= '(' && s1[i] != '[' && s1[i] != '{' && s1[i] != '<') {i=i+1;}. Можно было бы добавить еще сюда условие пока i!=dlina_stroki на случай если открывающейся скобки ниразу не встретилось, тогда в этом случае можно сразу реализовать выход из процедуры с сообщением об ошибке. Ну это ладно. Дальше что.
Предположим нашли мы эту скобку, а дальше я ее определяю, чтобы была известн как открывающаяся скобка, так и закрывающаяся.

switch (s1[i])
{
case '(': {ch=')'; ch_1='(';break;}
case '[': {ch=']'; ch_1='[';break;}
case '<': {ch='>'; ch_1='<';break;}
case '{': {ch='}'; ch_1='{';break;}
}
И после этого идет присваение n=i, это значит положение открывающейся скобки, которую мы нашли.

После этого нужно найти закрывающуюся скобку.
i=n+1; (будем искать закрывающуся скобку начиная со следующего положения)
kok=1; (этот счетчик сколько скобок мы нашли. 1 уже есть потому что одна скобка уже найдена.)

а дальше цикл do-while

do
{if (s1[i]==ch_1) kok=kok+1; (если нашли такую же скобку открытую то прибавим к счетчику)
if (s1[i]==ch) kok=kok-1; (если нашли такую скобку но закрытую, то вычитаем)
i=i+1;
} while (kok != 0 & i<=dlina_stroki); (пока kok не равен нулю и i меньше длины строки! хм. а почему здесь "и" ? вроде же...вроде "или" должен стоять! или или. blink.gif потом проверю)

после этого мы находим положение закрывающейся скобки и запоминаем его: k=i;

for (i=n; i<=k; i++)
printf("%c",s1[i]); //здесь мы печатаем от начальной скобки до конечной найденной.

потом..а здесь я смещаю положение, типа первая скобка была на i=n, а дальше мы прибавляем единичку и начинам проделывать тоже самое, тоесть идем в рекурсию, только уже i будет равно не 0, как изначально, а прибавленная на 1. n будет соответственно каждый раз разное, когда-нибудь i достигнет значиения длины строки и произойдет выход из процедуры, а пока что printf("\n%c",' '); таким образом я пытаюсь перевести укзаатель на новую строчку и вызываем f1(s1,i); с новым значением i
i=n+1;
if (i<dlina_stroki) { printf("\n%c",' '); f1(s1,i);}

Вроде логично.. вот только & там должен стоять или && надо проверить dry.gif

Сообщение отредактировано: Тёмный Эльф -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Гость






Цитата
только & там должен стоять или && надо проверить
А чего ты гадаешь? smile.gif & - это побитовая операция, && - логическая... В твоем случае нужна именно логическая, значит &&
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Цитата(volvo @ 30.04.2007 20:28) *

А чего ты гадаешь? smile.gif & - это побитовая операция, && - логическая... В твоем случае нужна именно логическая, значит &&

smile.gif

Добавлено через 15 мин.
Кое-что исправила. & на && заменила, но на каждый мой запрос прога выводила какие-то таинственные "(nu" заменила здесь
for (i=n; i<=k; i++)
printf("%c",s1[i]);
i<=k на i<k,
НО теперь в конце прога выводит не "(nu", а "(n". Откуда это вообще здесь берется?? blink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Гость






Ты упустила еще одно:
while (i <= dlina_stroki && s1[i]!= '(' && s1[i] != '[' && s1[i] != '{' && s1[i] != '<') { i=i+1; }

Обрати внимание на первую части условия - это надо контролировать всегда...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


точно. спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 26.11.2020 10:48
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name